Coverage Report

Created: 2026-06-10 06:56

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/brunsli/c/common/context.h
Line
Count
Source
1
// Copyright (c) Google LLC 2019
2
//
3
// Use of this source code is governed by an MIT-style
4
// license that can be found in the LICENSE file or at
5
// https://opensource.org/licenses/MIT.
6
7
#ifndef BRUNSLI_COMMON_CONTEXT_H_
8
#define BRUNSLI_COMMON_CONTEXT_H_
9
10
#include <vector>
11
12
#include "./distributions.h"
13
#include <brunsli/jpeg_data.h>
14
#include "./platform.h"
15
#include <brunsli/types.h>
16
17
namespace brunsli {
18
19
static const size_t kMaxAverageContext = 8;
20
static const size_t kNumAvrgContexts = kMaxAverageContext + 1u;
21
// 6 bits allow encoding values 0..63; this range represents the possible
22
// quantities of non-zero AC coefficients in the DCT block.
23
static const size_t kNumNonZeroBits = 6u;
24
/**
25
 * "number of non-zeros" value is decoded as a series of bits,
26
 * highest to lowest.
27
 *
28
 * Partially decoded value is used as a context for reading the next bit.
29
 * Contexts are organized in a binary tree. There are 64 final values, thus
30
 * there are 1-less non-leaf nodes.
31
 * Also, this constant also denotes the maximal value that could be encoded.
32
 *
33
 * static_assert(kNumNonZeroTreeSize == kDCTBlockSize - 1u)
34
 */
35
static const size_t kNumNonZeroTreeSize = (1u << kNumNonZeroBits) - 1u;
36
static const size_t kNumNonZeroQuant = 2u;
37
static const size_t kNumNonZeroContextMax =
38
    kNumNonZeroTreeSize / kNumNonZeroQuant;
39
static const size_t kNumNonZeroContextCount = kNumNonZeroContextMax + 1u;
40
41
static const uint8_t kNonzeroBuckets[64] = {
42
    0,  1,  2,  3,  4,  4,  5,  5,  5,  6,  6,  6,  6,  7,  7,  7,
43
    7,  7,  7,  7,  7,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
44
    9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  10, 10, 10,
45
    10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
46
};
47
// kNonzeroBuckets[i] < kNumNonzeroBuckets
48
static const uint8_t kNumNonzeroBuckets = 11;
49
50
static const int kNumSchemes = 7;
51
52
static const uint8_t kFreqContext[kNumSchemes][64] = {
53
    {
54
        0,
55
    },
56
57
    {
58
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
59
        0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
60
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,
61
    },
62
63
    {
64
        0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
65
        2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
66
        3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1,
67
    },
68
69
    {
70
        0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5,
71
        5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7,
72
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 2, 2, 2,
73
    },
74
75
    {
76
        0,  1,  2,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  8,  8,
77
        9,  9,  9,  9,  10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12,
78
        13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14,
79
        15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
80
    },
81
82
    {
83
        0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  10, 11, 12, 13, 14, 15,
84
        16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23,
85
        24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27,
86
        28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31,
87
    },
88
89
    {
90
        0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  10, 11, 12, 13, 14, 15,
91
        16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
92
        32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
93
        48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
94
    },
95
};
96
97
static const uint16_t kNumNonzeroContext[kNumSchemes][64] = {
98
    {0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5,
99
     5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7,
100
     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7},
101
    {0,  2,  2,  4,  4,  4,  6,  6,  6,  6,  8,  8,  8,  8,  8,  8,
102
     10, 10, 10, 10, 10, 10, 10, 10, 12, 12, 12, 12, 12, 12, 12, 12,
103
     12, 12, 12, 12, 12, 12, 12, 12, 14, 14, 14, 14, 14, 14, 14, 14,
104
     14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14},
105
    {0,  4,  4,  8,  8,  8,  12, 12, 12, 12, 16, 16, 16, 16, 16, 16,
106
     20, 20, 20, 20, 20, 20, 20, 20, 24, 24, 24, 24, 24, 24, 24, 24,
107
     24, 24, 24, 24, 24, 24, 24, 24, 28, 28, 28, 28, 28, 28, 28, 28,
108
     28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28},
109
    {0,  8,  8,  16, 16, 16, 24, 24, 24, 24, 32, 32, 32, 32, 32, 32,
110
     40, 40, 40, 40, 40, 40, 40, 40, 48, 48, 48, 48, 48, 48, 48, 48,
111
     48, 48, 48, 48, 48, 48, 48, 48, 55, 55, 55, 55, 55, 55, 55, 55,
112
     55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55},
113
    {0,   16,  16,  32,  32,  32,  48,  48,  48,  48,  64,  64,  64,
114
     64,  64,  64,  80,  80,  80,  80,  80,  80,  80,  80,  95,  95,
115
     95,  95,  95,  95,  95,  95,  95,  95,  95,  95,  95,  95,  95,
116
     95,  109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109,
117
     109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109},
118
    {0,   32,  32,  64,  64,  64,  96,  96,  96,  96,  127, 127, 127,
119
     127, 127, 127, 157, 157, 157, 157, 157, 157, 157, 157, 185, 185,
120
     185, 185, 185, 185, 185, 185, 185, 185, 185, 185, 185, 185, 185,
121
     185, 211, 211, 211, 211, 211, 211, 211, 211, 211, 211, 211, 211,
122
     211, 211, 211, 211, 211, 211, 211, 211, 211, 211, 211, 211},
123
    {0,   64,  64,  127, 127, 127, 188, 188, 188, 188, 246, 246, 246,
124
     246, 246, 246, 300, 300, 300, 300, 300, 300, 300, 300, 348, 348,
125
     348, 348, 348, 348, 348, 348, 348, 348, 348, 348, 348, 348, 348,
126
     348, 388, 388, 388, 388, 388, 388, 388, 388, 388, 388, 388, 388,
127
     388, 388, 388, 388, 388, 388, 388, 388, 388, 388, 388, 388}};
128
129
static const uint16_t kNumNonzeroContextSkip[kNumSchemes] = {8,   15,  31, 61,
130
                                                             120, 231, 412};
131
132
/**
133
 * Table that specifies, how context is calculated.
134
 *
135
 * Each value corresponds to DCT coefficient and is a sum of flags:
136
 *  - 1: context should be calculated using ACPredictContextRow
137
 *  - 2: context should be calculated using ACPredictContextCol
138
 */
139
static const uint8_t kContextAlgorithm[128] = {
140
    // JPEG XL layout
141
    0, 1, 1, 1, 1, 0, 0, 0,  //
142
    2, 3, 1, 1, 1, 0, 0, 0,  //
143
    2, 2, 0, 0, 0, 0, 0, 0,  //
144
    2, 2, 0, 0, 0, 0, 0, 0,  //
145
    2, 2, 0, 0, 0, 0, 0, 0,  //
146
    0, 0, 0, 0, 0, 0, 0, 0,  //
147
    0, 0, 0, 0, 0, 0, 0, 0,  //
148
    0, 0, 0, 0, 0, 0, 0, 0,
149
    // Legacy layout
150
    0, 1, 1, 1, 1, 1, 1, 1,  //
151
    2, 0, 0, 0, 0, 0, 0, 0,  //
152
    2, 0, 0, 0, 0, 0, 0, 0,  //
153
    2, 0, 0, 0, 0, 0, 0, 0,  //
154
    2, 0, 0, 0, 0, 0, 0, 0,  //
155
    2, 0, 0, 0, 0, 0, 0, 0,  //
156
    2, 0, 0, 0, 0, 0, 0, 0,  //
157
    2, 0, 0, 0, 0, 0, 0, 0,
158
};
159
160
inline uint16_t ZeroDensityContext(size_t nonzeros_left, size_t k,
161
10.5M
                                   size_t bits) {
162
10.5M
  return kNumNonzeroContext[bits][nonzeros_left] + kFreqContext[bits][k];
163
10.5M
}
164
165
// Returns the context for the absolute value of the prediction error of
166
// the next DC coefficient in column x, using the one row size ringbuffer of
167
// previous absolute prediction errors in vals.
168
3.29M
inline int WeightedAverageContextDC(const int* vals, int x) {
169
  // Since vals is a ringbuffer, vals[x] and vals[x + 1] refer to the
170
  // previous row.
171
3.29M
  int sum = 1 + vals[x - 2] + vals[x - 1] + vals[x] + vals[x + 1];
172
3.29M
  if ((sum >> kMaxAverageContext) != 0) {
173
139k
    return kMaxAverageContext;
174
139k
  }
175
3.15M
  return Log2FloorNonZero(sum);
176
3.29M
}
177
178
/**
179
 * Calculates the context on the base of average of already decoded
180
 * neighbour values.
181
 *
182
 * It is considered that vals[0] represents the value 2 rows above the current,
183
 * while the (locally) previous elements represent the current row. If y < 2,
184
 * then vals[0] should be 0.
185
 * Elements (locally) around vals[prev_row_delta] correspond to the row above
186
 * currnent one.
187
 *
188
 * Values are summed up with the following weights:
189
 *
190
 * 0|0|1|0
191
 * -+-+-+-
192
 * 0|1|2|1
193
 * -+-+-+-
194
 * 1|2|*|
195
 *     ^
196
 *     current position
197
 *
198
 * This method should not be invoked on the 0-th row or 0-th column.
199
 * It is also considered, that there are 2 extra fence columns before the 0-th
200
 * column and 1 fence column to the right of the last column,
201
 * all initialized with zeroes.
202
 */
203
5.87M
inline int WeightedAverageContext(const int* vals, int prev_row_delta) {
204
5.87M
  int sum = 4 + vals[0] + (vals[-kDCTBlockSize] + vals[prev_row_delta]) * 2 +
205
5.87M
            vals[-2 * kDCTBlockSize] + vals[prev_row_delta - kDCTBlockSize] +
206
5.87M
            vals[prev_row_delta + kDCTBlockSize];
207
5.87M
  if ((sum >> (kMaxAverageContext + 2)) != 0) {
208
1.85M
    return kMaxAverageContext;
209
1.85M
  }
210
4.01M
  return Log2FloorNonZero(sum) - 2;
211
5.87M
}
212
213
static const int kACPredictPrecisionBits = 13;
214
static const int kACPredictPrecision = 1 << kACPredictPrecisionBits;
215
216
void ComputeACPredictMultipliers(const int* quant, int* mult_row,
217
                                 int* mult_col);
218
219
// Computes average and sign context from the AC prediction.
220
4.49M
inline void ACPredictContext(int64_t p, size_t* avg_ctx, size_t* sgn) {
221
4.49M
  int multiplier;
222
4.49M
  if (p >= 0) {
223
2.66M
    multiplier = 1;
224
2.66M
  } else {
225
1.82M
    multiplier = -1;
226
1.82M
    p = -p;
227
1.82M
  }
228
4.49M
  size_t ctx;
229
4.49M
  if (p >= (1u << kMaxAverageContext)) {
230
2.95M
    ctx = kMaxAverageContext;
231
2.95M
  } else {
232
    // 0 -> 0, 1 -> 1, 2..3 -> 2, 4..7 -> 3, etc.
233
1.54M
    ctx = Log2FloorNonZero(2 * static_cast<uint32_t>(p)+ 1);
234
1.54M
  }
235
4.49M
  *avg_ctx = ctx;
236
4.49M
  *sgn = kMaxAverageContext + multiplier * ctx;
237
4.49M
}
238
239
inline void ACPredictContextCol(const coeff_t* prev, const coeff_t* cur,
240
2.43M
                                const int* mult, size_t* avg_ctx, size_t* sgn) {
241
2.43M
  coeff_t terms[8];
242
2.43M
  terms[0] = 0;
243
2.43M
  terms[1] = cur[1] + prev[1];
244
2.43M
  terms[2] = cur[2] - prev[2];
245
2.43M
  terms[3] = cur[3] + prev[3];
246
2.43M
  terms[4] = cur[4] - prev[4];
247
2.43M
  terms[5] = cur[5] + prev[5];
248
2.43M
  terms[6] = cur[6] - prev[6];
249
2.43M
  terms[7] = cur[7] + prev[7];
250
2.43M
  int64_t delta = terms[0] * static_cast<int64_t>(mult[0]) +
251
2.43M
                  terms[1] * static_cast<int64_t>(mult[1]) +
252
2.43M
                  terms[2] * static_cast<int64_t>(mult[2]) +
253
2.43M
                  terms[3] * static_cast<int64_t>(mult[3]) +
254
2.43M
                  terms[4] * static_cast<int64_t>(mult[4]) +
255
2.43M
                  terms[5] * static_cast<int64_t>(mult[5]) +
256
2.43M
                  terms[6] * static_cast<int64_t>(mult[6]) +
257
2.43M
                  terms[7] * static_cast<int64_t>(mult[7]);
258
2.43M
  ACPredictContext(prev[0] - delta / kACPredictPrecision, avg_ctx, sgn);
259
2.43M
}
260
261
inline void ACPredictContextRow(const coeff_t* prev, const coeff_t* cur,
262
2.06M
                               const int* mult, size_t* avg_ctx, size_t* sgn) {
263
2.06M
  coeff_t terms[8];
264
2.06M
  terms[0] = 0;
265
2.06M
  terms[1] = cur[8] + prev[8];
266
2.06M
  terms[2] = cur[16] - prev[16];
267
2.06M
  terms[3] = cur[24] + prev[24];
268
2.06M
  terms[4] = cur[32] - prev[32];
269
2.06M
  terms[5] = cur[40] + prev[40];
270
2.06M
  terms[6] = cur[48] - prev[48];
271
2.06M
  terms[7] = cur[56] + prev[56];
272
2.06M
  int64_t delta = terms[0] * static_cast<int64_t>(mult[0]) +
273
2.06M
                  terms[1] * static_cast<int64_t>(mult[1]) +
274
2.06M
                  terms[2] * static_cast<int64_t>(mult[2]) +
275
2.06M
                  terms[3] * static_cast<int64_t>(mult[3]) +
276
2.06M
                  terms[4] * static_cast<int64_t>(mult[4]) +
277
2.06M
                  terms[5] * static_cast<int64_t>(mult[5]) +
278
2.06M
                  terms[6] * static_cast<int64_t>(mult[6]) +
279
2.06M
                  terms[7] * static_cast<int64_t>(mult[7]);
280
2.06M
  ACPredictContext(prev[0] - delta / kACPredictPrecision, avg_ctx, sgn);
281
2.06M
}
282
283
/**
284
 * PRECONDITION: 0 <= prev[i] <= 63
285
 * PRECONDITION: elements of prev at and after x correspond to previous
286
 *               row; elements before x correspond to current row
287
 */
288
3.90M
inline uint8_t NumNonzerosContext(const uint8_t* prev, int x, int y) {
289
3.90M
  size_t prediction;
290
3.90M
  if (y == 0) {
291
300k
    if (x == 0) {
292
      // Special case: top-left block.
293
6.16k
      prediction = 0;
294
293k
    } else {
295
      // No row above; use block at left.
296
293k
      prediction = prev[x - 1];
297
293k
    }
298
3.60M
  } else if (x == 0) {
299
    // No column to the left; use block above.
300
74.7k
    prediction = prev[x];
301
3.52M
  } else {
302
    // Average of left and above blocks.
303
3.52M
    prediction = (prev[x - 1] + prev[x] + 1) / 2;
304
3.52M
  }
305
3.90M
  BRUNSLI_DCHECK(prediction <= kNumNonZeroTreeSize);
306
3.90M
  return static_cast<uint8_t>(prediction / kNumNonZeroQuant);
307
3.90M
}
308
309
// Context for the emptyness of a block is the number of non-empty blocks in the
310
// previous and up neighborhood (blocks beyond the border are assumed
311
// non-empty).
312
static const int kNumIsEmptyBlockContexts = 3;
313
65.9M
inline int IsEmptyBlockContext(const int* prev, int x) {
314
65.9M
  return prev[x - 1] + prev[x];
315
65.9M
}
316
317
// Holds all encoding/decoding state for an image component that is needed to
318
// switch between components during interleaved encoding/decoding.
319
struct ComponentStateDC {
320
  ComponentStateDC()
321
12.6k
      : width(0),
322
12.6k
        is_empty_block_prob(kNumIsEmptyBlockContexts),
323
12.6k
        sign_prob(9),
324
12.6k
        first_extra_bit_prob(10) {
325
12.6k
    InitAll();
326
12.6k
  }
327
328
12.6k
  void SetWidth(int w) {
329
12.6k
    width = w;
330
12.6k
    prev_is_nonempty.resize(w + 1, 1);
331
12.6k
    prev_abs_coeff.resize(w + 3);
332
12.6k
    prev_sign.resize(w + 1);
333
12.6k
  }
334
335
  int width;
336
  Prob is_zero_prob;
337
  std::vector<Prob> is_empty_block_prob;
338
  std::vector<Prob> sign_prob;
339
  std::vector<Prob> first_extra_bit_prob;
340
  std::vector<int> prev_is_nonempty;
341
  std::vector<int> prev_abs_coeff;
342
  std::vector<int> prev_sign;
343
344
 protected:
345
  void InitAll();
346
};
347
348
struct ComponentState {
349
  ComponentState()
350
11.4k
      : width(0),
351
11.4k
        is_zero_prob(kNumNonzeroBuckets * kDCTBlockSize),
352
11.4k
        sign_prob((2 * kMaxAverageContext + 1) * kDCTBlockSize),
353
11.4k
        first_extra_bit_prob(10 * kDCTBlockSize) {
354
11.4k
    InitAll();
355
11.4k
  }
356
357
11.4k
  void SetWidth(int w) {
358
11.4k
    width = w;
359
11.4k
    prev_is_nonempty.resize(w + 1, 1);
360
11.4k
    prev_num_nonzeros.resize(w);
361
11.4k
    prev_abs_coeff.resize(kDCTBlockSize * 2 * (w + 3));
362
11.4k
    prev_sign.resize(kDCTBlockSize * (w + 1));
363
11.4k
  }
364
365
  // Returns the size of the object after constructor and SetWidth(w).
366
  // Used in estimating peak heap memory usage of the brunsli codec.
367
0
  static size_t SizeInBytes(int w) {
368
0
    return (4 + (10 + 3 * w) * kDCTBlockSize + 2 * w) * sizeof(int) +
369
0
           ((kNumNonzeroBuckets + 2 * kMaxAverageContext + 11) * kDCTBlockSize +
370
0
            kNumNonZeroContextCount * kNumNonZeroTreeSize) *
371
0
               sizeof(Prob);
372
0
  }
373
374
  int width;
375
  int context_offset;
376
  uint32_t order[kDCTBlockSize];
377
  int mult_row[kDCTBlockSize];
378
  // mult_col is transposed for more effective ACPredictContextRow execution.
379
  int mult_col[kDCTBlockSize];
380
  std::vector<Prob> is_zero_prob;
381
  std::vector<Prob> sign_prob;
382
  Prob num_nonzero_prob[kNumNonZeroContextCount * kNumNonZeroTreeSize];
383
  std::vector<Prob> first_extra_bit_prob;
384
  std::vector<int> prev_is_nonempty;
385
  std::vector<uint8_t> prev_num_nonzeros;
386
  std::vector<int> prev_abs_coeff;
387
  std::vector<int> prev_sign;
388
389
 protected:
390
  void InitAll();
391
};
392
393
}  // namespace brunsli
394
395
#endif  // BRUNSLI_COMMON_CONTEXT_H_