Coverage Report

Created: 2022-08-24 06:15

/src/x265/source/encoder/search.h
Line
Count
Source (jump to first uncovered line)
1
/*****************************************************************************
2
* Copyright (C) 2013-2020 MulticoreWare, Inc
3
*
4
* Authors: Steve Borho <steve@borho.org>
5
*          Min Chen <chenm003@163.com>
6
*
7
* This program is free software; you can redistribute it and/or modify
8
* it under the terms of the GNU General Public License as published by
9
* the Free Software Foundation; either version 2 of the License, or
10
* (at your option) any later version.
11
*
12
* This program is distributed in the hope that it will be useful,
13
* but WITHOUT ANY WARRANTY; without even the implied warranty of
14
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
* GNU General Public License for more details.
16
*
17
* You should have received a copy of the GNU General Public License
18
* along with this program; if not, write to the Free Software
19
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02111, USA.
20
*
21
* This program is also available under a commercial proprietary license.
22
* For more information, contact us at license @ x265.com.
23
*****************************************************************************/
24
25
#ifndef X265_SEARCH_H
26
#define X265_SEARCH_H
27
28
#include "common.h"
29
#include "predict.h"
30
#include "quant.h"
31
#include "bitcost.h"
32
#include "framedata.h"
33
#include "yuv.h"
34
#include "threadpool.h"
35
36
#include "rdcost.h"
37
#include "entropy.h"
38
#include "motion.h"
39
40
#if DETAILED_CU_STATS
41
#define ProfileCUScopeNamed(name, cu, acc, count) \
42
    m_stats[cu.m_encData->m_frameEncoderID].count++; \
43
    ScopedElapsedTime name(m_stats[cu.m_encData->m_frameEncoderID].acc)
44
#define ProfileCUScope(cu, acc, count) ProfileCUScopeNamed(timedScope, cu, acc, count)
45
#define ProfileCounter(cu, count) m_stats[cu.m_encData->m_frameEncoderID].count++;
46
#else
47
#define ProfileCUScopeNamed(name, cu, acc, count)
48
#define ProfileCUScope(cu, acc, count)
49
#define ProfileCounter(cu, count)
50
#endif
51
52
#define NUM_SUBPART MAX_TS_SIZE * 4 // 4 sub partitions * 4 depth
53
54
namespace X265_NS {
55
// private namespace
56
57
class Entropy;
58
struct ThreadLocalData;
59
60
/* All the CABAC contexts that Analysis needs to keep track of at each depth
61
 * and temp buffers for residual, coeff, and recon for use during residual
62
 * quad-tree depth recursion */
63
struct RQTData
64
{
65
    Entropy  cur;     /* starting context for current CU */
66
67
    /* these are indexed by qtLayer (log2size - 2) so nominally 0=4x4, 1=8x8, 2=16x16, 3=32x32
68
     * the coeffRQT and reconQtYuv are allocated to the max CU size at every depth. The parts
69
     * which are reconstructed at each depth are valid. At the end, the transform depth table
70
     * is walked and the coeff and recon at the final split depths are collected */
71
    Entropy  rqtRoot;      /* residual quad-tree start context */
72
    Entropy  rqtTemp;      /* residual quad-tree temp context */
73
    Entropy  rqtTest;      /* residual quad-tree test context */
74
    coeff_t* coeffRQT[3];  /* coeff storage for entire CTU for each RQT layer */
75
    Yuv      reconQtYuv;   /* recon storage for entire CTU for each RQT layer (intra) */
76
    ShortYuv resiQtYuv;    /* residual storage for entire CTU for each RQT layer (inter) */
77
    
78
    /* per-depth temp buffers for inter prediction */
79
    ShortYuv tmpResiYuv;
80
    Yuv      tmpPredYuv;
81
    Yuv      bidirPredYuv[2];
82
};
83
84
struct MotionData
85
{
86
    MV       mv;
87
    MV       mvp;
88
    int      mvpIdx;
89
    int      ref;
90
    int      bits;
91
    uint32_t mvCost;
92
    uint32_t cost;
93
94
    MotionData()
95
5.07M
    {
96
5.07M
        memset(this, 0, sizeof(MotionData));
97
5.07M
    }
98
};
99
100
struct Mode
101
{
102
    CUData     cu;
103
    const Yuv* fencYuv;
104
    Yuv        predYuv;
105
    Yuv        reconYuv;
106
    Entropy    contexts;
107
108
    enum { MAX_INTER_PARTS = 2 };
109
110
    MotionData bestME[MAX_INTER_PARTS][2];
111
    MV         amvpCand[2][MAX_NUM_REF][AMVP_NUM_CANDS];
112
113
    // Neighbour MVs of the current partition. 5 spatial candidates and the
114
    // temporal candidate.
115
    InterNeighbourMV interNeighbours[6];
116
117
    uint64_t    rdCost;     // sum of partition (psy) RD costs          (sse(fenc, recon) + lambda2 * bits)
118
    uint64_t    sa8dCost;   // sum of partition sa8d distortion costs   (sa8d(fenc, pred) + lambda * bits)
119
    uint32_t    sa8dBits;   // signal bits used in sa8dCost calculation
120
    uint32_t    psyEnergy;  // sum of partition psycho-visual energy difference
121
    uint32_t    ssimEnergy;
122
    sse_t   resEnergy;  // sum of partition residual energy after motion prediction
123
    sse_t   lumaDistortion;
124
    sse_t   chromaDistortion;
125
    sse_t  distortion; // sum of partition SSE distortion
126
    uint32_t    totalBits;  // sum of partition bits (mv + coeff)
127
    uint32_t    mvBits;     // Mv bits + Ref + block type (or intra mode)
128
    uint32_t    coeffBits;  // Texture bits (DCT Coeffs)
129
130
    void initCosts()
131
890k
    {
132
890k
        rdCost = 0;
133
890k
        sa8dCost = 0;
134
890k
        sa8dBits = 0;
135
890k
        psyEnergy = 0;
136
890k
        ssimEnergy = 0;
137
890k
        resEnergy = 0;
138
890k
        lumaDistortion = 0;
139
890k
        chromaDistortion = 0;
140
890k
        distortion = 0;
141
890k
        totalBits = 0;
142
890k
        mvBits = 0;
143
890k
        coeffBits = 0;
144
890k
    }
145
146
    void addSubCosts(const Mode& subMode)
147
440k
    {
148
440k
        rdCost += subMode.rdCost;
149
440k
        sa8dCost += subMode.sa8dCost;
150
440k
        sa8dBits += subMode.sa8dBits;
151
440k
        psyEnergy += subMode.psyEnergy;
152
440k
        ssimEnergy += subMode.ssimEnergy;
153
440k
        resEnergy += subMode.resEnergy;
154
440k
        lumaDistortion += subMode.lumaDistortion;
155
440k
        chromaDistortion += subMode.chromaDistortion;
156
440k
        distortion += subMode.distortion;
157
440k
        totalBits += subMode.totalBits;
158
440k
        mvBits += subMode.mvBits;
159
440k
        coeffBits += subMode.coeffBits;
160
440k
    }
161
};
162
163
#if DETAILED_CU_STATS
164
/* This structure is intended for performance debugging and we make no attempt
165
 * to handle dynamic range overflows. Care should be taken to avoid long encodes
166
 * if you care about the accuracy of these elapsed times and counters. This
167
 * profiling is orthogonal to PPA/VTune and can be enabled independently from
168
 * either of them */
169
struct CUStats
170
{
171
    int64_t  intraRDOElapsedTime[NUM_CU_DEPTH]; // elapsed worker time in intra RDO per CU depth
172
    int64_t  interRDOElapsedTime[NUM_CU_DEPTH]; // elapsed worker time in inter RDO per CU depth
173
    int64_t  intraAnalysisElapsedTime;          // elapsed worker time in intra sa8d analysis
174
    int64_t  motionEstimationElapsedTime;       // elapsed worker time in predInterSearch()
175
    int64_t  loopFilterElapsedTime;             // elapsed worker time in deblock and SAO and PSNR/SSIM
176
    int64_t  pmeTime;                           // elapsed worker time processing ME slave jobs
177
    int64_t  pmeBlockTime;                      // elapsed worker time blocked for pme batch completion
178
    int64_t  pmodeTime;                         // elapsed worker time processing pmode slave jobs
179
    int64_t  pmodeBlockTime;                    // elapsed worker time blocked for pmode batch completion
180
    int64_t  weightAnalyzeTime;                 // elapsed worker time analyzing reference weights
181
    int64_t  totalCTUTime;                      // elapsed worker time in compressCTU (includes pmode master)
182
183
    uint32_t skippedMotionReferences[NUM_CU_DEPTH];
184
    uint32_t totalMotionReferences[NUM_CU_DEPTH];
185
    uint32_t skippedIntraCU[NUM_CU_DEPTH];
186
    uint32_t totalIntraCU[NUM_CU_DEPTH];
187
188
    uint64_t countIntraRDO[NUM_CU_DEPTH];
189
    uint64_t countInterRDO[NUM_CU_DEPTH];
190
    uint64_t countIntraAnalysis;
191
    uint64_t countMotionEstimate;
192
    uint64_t countLoopFilter;
193
    uint64_t countPMETasks;
194
    uint64_t countPMEMasters;
195
    uint64_t countPModeTasks;
196
    uint64_t countPModeMasters;
197
    uint64_t countWeightAnalyze;
198
    uint64_t totalCTUs;
199
200
    CUStats() { clear(); }
201
202
    void clear()
203
    {
204
        memset(this, 0, sizeof(*this));
205
    }
206
207
    void accumulate(CUStats& other, x265_param& param)
208
    {
209
        for (uint32_t i = 0; i <= param.maxCUDepth; i++)
210
        {
211
            intraRDOElapsedTime[i] += other.intraRDOElapsedTime[i];
212
            interRDOElapsedTime[i] += other.interRDOElapsedTime[i];
213
            countIntraRDO[i] += other.countIntraRDO[i];
214
            countInterRDO[i] += other.countInterRDO[i];
215
            skippedMotionReferences[i] += other.skippedMotionReferences[i];
216
            totalMotionReferences[i] += other.totalMotionReferences[i];
217
            skippedIntraCU[i] += other.skippedIntraCU[i];
218
            totalIntraCU[i] += other.totalIntraCU[i];
219
        }
220
221
        intraAnalysisElapsedTime += other.intraAnalysisElapsedTime;
222
        motionEstimationElapsedTime += other.motionEstimationElapsedTime;
223
        loopFilterElapsedTime += other.loopFilterElapsedTime;
224
        pmeTime += other.pmeTime;
225
        pmeBlockTime += other.pmeBlockTime;
226
        pmodeTime += other.pmodeTime;
227
        pmodeBlockTime += other.pmodeBlockTime;
228
        weightAnalyzeTime += other.weightAnalyzeTime;
229
        totalCTUTime += other.totalCTUTime;
230
231
        countIntraAnalysis += other.countIntraAnalysis;
232
        countMotionEstimate += other.countMotionEstimate;
233
        countLoopFilter += other.countLoopFilter;
234
        countPMETasks += other.countPMETasks;
235
        countPMEMasters += other.countPMEMasters;
236
        countPModeTasks += other.countPModeTasks;
237
        countPModeMasters += other.countPModeMasters;
238
        countWeightAnalyze += other.countWeightAnalyze;
239
        totalCTUs += other.totalCTUs;
240
241
        other.clear();
242
    }
243
}; 
244
#endif
245
246
inline int getTUBits(int idx, int numIdx)
247
0
{
248
0
    return idx + (idx < numIdx - 1);
249
0
}
250
251
class Search : public Predict
252
{
253
public:
254
255
    static const int16_t zeroShort[MAX_CU_SIZE];
256
257
    MotionEstimate  m_me;
258
    Quant           m_quant;
259
    RDCost          m_rdCost;
260
    const x265_param* m_param;
261
    Frame*          m_frame;
262
    const Slice*    m_slice;
263
264
    Entropy         m_entropyCoder;
265
    RQTData         m_rqt[NUM_FULL_DEPTH];
266
267
    uint8_t*        m_qtTempCbf[3];
268
    uint8_t*        m_qtTempTransformSkipFlag[3];
269
270
    pixel*          m_fencScaled;     /* 32x32 buffer for down-scaled version of 64x64 CU fenc */
271
    pixel*          m_fencTransposed; /* 32x32 buffer for transposed copy of fenc */
272
    pixel*          m_intraPred;      /* 32x32 buffer for individual intra predictions */
273
    pixel*          m_intraPredAngs;  /* allocation for 33 consecutive (all angular) 32x32 intra predictions */
274
275
    coeff_t*        m_tsCoeff;        /* transform skip coeff 32x32 */
276
    int16_t*        m_tsResidual;     /* transform skip residual 32x32 */
277
    pixel*          m_tsRecon;        /* transform skip reconstructed pixels 32x32 */
278
279
    bool            m_bFrameParallel;
280
    uint32_t        m_numLayers;
281
    uint32_t        m_refLagPixels;
282
283
    int32_t         m_maxTUDepth;
284
    uint16_t        m_limitTU;
285
286
    int32_t         m_sliceMaxY;
287
    int32_t         m_sliceMinY;
288
289
#if DETAILED_CU_STATS
290
    /* Accumulate CU statistics separately for each frame encoder */
291
    CUStats         m_stats[X265_MAX_FRAME_THREADS];
292
#endif
293
294
    Search();
295
    ~Search();
296
297
    bool     initSearch(const x265_param& param, ScalingList& scalingList);
298
    int      setLambdaFromQP(const CUData& ctu, int qp, int lambdaQP = -1); /* returns real quant QP in valid spec range */
299
300
    // mark temp RD entropy contexts as uninitialized; useful for finding loads without stores
301
    void     invalidateContexts(int fromDepth);
302
303
    // full RD search of intra modes
304
    void     checkIntra(Mode& intraMode, const CUGeom& cuGeom, PartSize partSizes);
305
306
    // select best intra mode using only sa8d costs, cannot measure NxN intra
307
    void     checkIntraInInter(Mode& intraMode, const CUGeom& cuGeom);
308
    // encode luma mode selected by checkIntraInInter, then pick and encode a chroma mode
309
    void     encodeIntraInInter(Mode& intraMode, const CUGeom& cuGeom);
310
311
    // estimation inter prediction (non-skip)
312
    void     predInterSearch(Mode& interMode, const CUGeom& cuGeom, bool bChromaMC, uint32_t masks[2]);
313
    void     searchMV(Mode& interMode, int list, int ref, MV& outmv, MV mvp[3], int numMvc, MV* mvc);
314
    // encode residual and compute rd-cost for inter mode
315
    void     encodeResAndCalcRdInterCU(Mode& interMode, const CUGeom& cuGeom);
316
    void     encodeResAndCalcRdSkipCU(Mode& interMode);
317
318
    // encode residual without rd-cost
319
    void     residualTransformQuantInter(Mode& mode, const CUGeom& cuGeom, uint32_t absPartIdx, uint32_t tuDepth, const uint32_t depthRange[2]);
320
    void     residualTransformQuantIntra(Mode& mode, const CUGeom& cuGeom, uint32_t absPartIdx, uint32_t tuDepth, const uint32_t depthRange[2]);
321
    void     residualQTIntraChroma(Mode& mode, const CUGeom& cuGeom, uint32_t absPartIdx, uint32_t tuDepth);
322
323
    // pick be chroma mode from available using just sa8d costs
324
    void     getBestIntraModeChroma(Mode& intraMode, const CUGeom& cuGeom);
325
326
    /* update CBF flags and QP values to be internally consistent */
327
    void checkDQP(Mode& mode, const CUGeom& cuGeom);
328
    void checkDQPForSplitPred(Mode& mode, const CUGeom& cuGeom);
329
330
    MV getLowresMV(const CUData& cu, const PredictionUnit& pu, int list, int ref);
331
332
    class PME : public BondedTaskGroup
333
    {
334
    public:
335
336
        Search&       master;
337
        Mode&         mode;
338
        const CUGeom& cuGeom;
339
        const PredictionUnit& pu;
340
        int           puIdx;
341
342
        struct {
343
            int ref[2][MAX_NUM_REF];
344
            int refCnt[2];
345
        } m_jobs;
346
347
0
        PME(Search& s, Mode& m, const CUGeom& g, const PredictionUnit& u, int p) : master(s), mode(m), cuGeom(g), pu(u), puIdx(p) {}
348
349
        void processTasks(int workerThreadId);
350
351
    protected:
352
353
        PME operator=(const PME&);
354
    };
355
356
    void     processPME(PME& pme, Search& slave);
357
    void     singleMotionEstimation(Search& master, Mode& interMode, const PredictionUnit& pu, int part, int list, int ref);
358
359
protected:
360
361
    /* motion estimation distribution */
362
    ThreadLocalData* m_tld;
363
364
    uint32_t      m_listSelBits[3];
365
    Lock          m_meLock;
366
367
    void     saveResidualQTData(CUData& cu, ShortYuv& resiYuv, uint32_t absPartIdx, uint32_t tuDepth);
368
369
    // RDO search of luma intra modes; result is fully encoded luma. luma distortion is returned
370
    sse_t estIntraPredQT(Mode &intraMode, const CUGeom& cuGeom, const uint32_t depthRange[2]);
371
372
    // RDO select best chroma mode from luma; result is fully encode chroma. chroma distortion is returned
373
    sse_t estIntraPredChromaQT(Mode &intraMode, const CUGeom& cuGeom);
374
375
    void     codeSubdivCbfQTChroma(const CUData& cu, uint32_t tuDepth, uint32_t absPartIdx);
376
    void     codeInterSubdivCbfQT(CUData& cu, uint32_t absPartIdx, const uint32_t tuDepth, const uint32_t depthRange[2]);
377
    void     codeCoeffQTChroma(const CUData& cu, uint32_t tuDepth, uint32_t absPartIdx, TextType ttype);
378
379
    struct Cost
380
    {
381
        uint64_t rdcost;
382
        uint32_t bits;
383
        sse_t distortion;
384
        uint32_t energy;
385
13.4M
        Cost() { rdcost = 0; bits = 0; distortion = 0; energy = 0; }
386
    };
387
388
    struct TUInfoCache
389
    {
390
        Cost cost[NUM_SUBPART];
391
        uint32_t bestTransformMode[NUM_SUBPART][MAX_NUM_COMPONENT][2];
392
        uint8_t cbfFlag[NUM_SUBPART][MAX_NUM_COMPONENT][2];
393
        Entropy rqtStore[NUM_SUBPART];
394
    } m_cacheTU;
395
396
    uint64_t estimateNullCbfCost(sse_t dist, uint32_t energy, uint32_t tuDepth, TextType compId);
397
    bool     splitTU(Mode& mode, const CUGeom& cuGeom, uint32_t absPartIdx, uint32_t tuDepth, ShortYuv& resiYuv, Cost& splitCost, const uint32_t depthRange[2], int32_t splitMore);
398
    void     estimateResidualQT(Mode& mode, const CUGeom& cuGeom, uint32_t absPartIdx, uint32_t depth, ShortYuv& resiYuv, Cost& costs, const uint32_t depthRange[2], int32_t splitMore = -1);
399
400
    // generate prediction, generate residual and recon. if bAllowSplit, find optimal RQT splits
401
    void     codeIntraLumaQT(Mode& mode, const CUGeom& cuGeom, uint32_t tuDepth, uint32_t absPartIdx, bool bAllowSplit, Cost& costs, const uint32_t depthRange[2]);
402
    void     codeIntraLumaTSkip(Mode& mode, const CUGeom& cuGeom, uint32_t tuDepth, uint32_t absPartIdx, Cost& costs);
403
    void     extractIntraResultQT(CUData& cu, Yuv& reconYuv, uint32_t tuDepth, uint32_t absPartIdx);
404
405
    // generate chroma prediction, generate residual and recon
406
    void     codeIntraChromaQt(Mode& mode, const CUGeom& cuGeom, uint32_t tuDepth, uint32_t absPartIdx, Cost& outCost);
407
    void     codeIntraChromaTSkip(Mode& mode, const CUGeom& cuGeom, uint32_t tuDepth, uint32_t tuDepthC, uint32_t absPartIdx, Cost& outCost);
408
    void     extractIntraResultChromaQT(CUData& cu, Yuv& reconYuv, uint32_t absPartIdx, uint32_t tuDepth);
409
410
    // reshuffle CBF flags after coding a pair of 4:2:2 chroma blocks
411
    void     offsetSubTUCBFs(CUData& cu, TextType ttype, uint32_t tuDepth, uint32_t absPartIdx);
412
413
    /* output of mergeEstimation, best merge candidate */
414
    struct MergeData
415
    {
416
        MVField  mvField[2];
417
        uint32_t dir;
418
        uint32_t index;
419
        uint32_t bits;
420
    };
421
422
    /* inter/ME helper functions */
423
    int       selectMVP(const CUData& cu, const PredictionUnit& pu, const MV amvp[AMVP_NUM_CANDS], int list, int ref);
424
    const MV& checkBestMVP(const MV amvpCand[2], const MV& mv, int& mvpIdx, uint32_t& outBits, uint32_t& outCost) const;
425
    void     setSearchRange(const CUData& cu, const MV& mvp, int merange, MV& mvmin, MV& mvmax) const;
426
    uint32_t mergeEstimation(CUData& cu, const CUGeom& cuGeom, const PredictionUnit& pu, int puIdx, MergeData& m);
427
    static void getBlkBits(PartSize cuMode, bool bPSlice, int puIdx, uint32_t lastMode, uint32_t blockBit[3]);
428
    void      updateMVP(const MV amvp, const MV& mv, uint32_t& outBits, uint32_t& outCost, const MV& alterMVP);
429
430
    /* intra helper functions */
431
    enum { MAX_RD_INTRA_MODES = 16 };
432
    static void updateCandList(uint32_t mode, uint64_t cost, int maxCandCount, uint32_t* candModeList, uint64_t* candCostList);
433
434
    // get most probable luma modes for CU part, and bit cost of all non mpm modes
435
    uint32_t getIntraRemModeBits(CUData & cu, uint32_t absPartIdx, uint32_t mpmModes[3], uint64_t& mpms) const;
436
437
991k
    void updateModeCost(Mode& m) const { m.rdCost = m_rdCost.m_psyRd ? m_rdCost.calcPsyRdCost(m.distortion, m.totalBits, m.psyEnergy)
438
18.4E
                                                : (m_rdCost.m_ssimRd ? m_rdCost.calcSsimRdCost(m.distortion, m.totalBits, m.ssimEnergy) 
439
18.4E
                                                : m_rdCost.calcRdCost(m.distortion, m.totalBits)); }
440
};
441
}
442
443
#endif // ifndef X265_SEARCH_H