Coverage Report

Created: 2026-09-14 07:04

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