| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * H.274 film grain synthesis | ||
| 3 | * Copyright (c) 2021 Niklas Haas <ffmpeg@haasn.xyz> | ||
| 4 | * | ||
| 5 | * This file is part of FFmpeg. | ||
| 6 | * | ||
| 7 | * FFmpeg is free software; you can redistribute it and/or | ||
| 8 | * modify it under the terms of the GNU Lesser General Public | ||
| 9 | * License as published by the Free Software Foundation; either | ||
| 10 | * version 2.1 of the License, or (at your option) any later version. | ||
| 11 | * | ||
| 12 | * FFmpeg 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 GNU | ||
| 15 | * Lesser General Public License for more details. | ||
| 16 | * | ||
| 17 | * You should have received a copy of the GNU Lesser General Public | ||
| 18 | * License along with FFmpeg; if not, write to the Free Software | ||
| 19 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | ||
| 20 | */ | ||
| 21 | |||
| 22 | /** | ||
| 23 | * @file | ||
| 24 | * H.274 film grain synthesis. | ||
| 25 | * @author Niklas Haas <ffmpeg@haasn.xyz> | ||
| 26 | */ | ||
| 27 | |||
| 28 | #include <stdatomic.h> | ||
| 29 | |||
| 30 | #include "libavutil/avassert.h" | ||
| 31 | #include "libavutil/bswap.h" | ||
| 32 | #include "libavcodec/bswapdsp.h" | ||
| 33 | #include "libavutil/crc.h" | ||
| 34 | #include "libavutil/imgutils.h" | ||
| 35 | #include "libavutil/md5.h" | ||
| 36 | #include "libavutil/mem.h" | ||
| 37 | #include "libavutil/thread.h" | ||
| 38 | |||
| 39 | #include "h274.h" | ||
| 40 | |||
| 41 | typedef struct H274FilmGrainDatabase { | ||
| 42 | // Database of film grain patterns, lazily computed as-needed | ||
| 43 | int8_t db[13 /* h */][13 /* v */][64][64]; | ||
| 44 | atomic_uint residency[6]; | ||
| 45 | } H274FilmGrainDatabase; | ||
| 46 | |||
| 47 | static H274FilmGrainDatabase film_grain_db; | ||
| 48 | |||
| 49 | static const int8_t Gaussian_LUT[2048+4]; | ||
| 50 | static const uint32_t Seed_LUT[256]; | ||
| 51 | static const int8_t R64T[64][64]; | ||
| 52 | |||
| 53 | ✗ | static void prng_shift(uint32_t *state) | |
| 54 | { | ||
| 55 | // Primitive polynomial x^31 + x^3 + 1 (modulo 2) | ||
| 56 | ✗ | uint32_t x = *state; | |
| 57 | ✗ | uint8_t feedback = 1u ^ (x >> 2) ^ (x >> 30); | |
| 58 | ✗ | *state = (x << 1) | (feedback & 1u); | |
| 59 | ✗ | } | |
| 60 | |||
| 61 | ✗ | static void init_slice_c(int8_t out[64][64], uint8_t h, uint8_t v) | |
| 62 | { | ||
| 63 | static const uint8_t deblock_factors[13] = { | ||
| 64 | 64, 71, 77, 84, 90, 96, 103, 109, 116, 122, 128, 128, 128 | ||
| 65 | }; | ||
| 66 | |||
| 67 | ✗ | const uint8_t deblock_coeff = deblock_factors[v]; | |
| 68 | ✗ | const uint8_t freq_h = ((h + 3) << 2) - 1; | |
| 69 | ✗ | const uint8_t freq_v = ((v + 3) << 2) - 1; | |
| 70 | // Temporary buffer for slice generation | ||
| 71 | // FIXME: Static or not? | ||
| 72 | static int16_t tmp[64][64]; | ||
| 73 | ✗ | uint32_t seed = Seed_LUT[h + v * 13]; | |
| 74 | |||
| 75 | // Initialize with random gaussian values, using the output array as a | ||
| 76 | // temporary buffer for these intermediate values. | ||
| 77 | // | ||
| 78 | // Note: To make the subsequent matrix multiplication cache friendlier, we | ||
| 79 | // store each *column* of the starting image in a *row* of `out` | ||
| 80 | ✗ | for (int l = 0; l <= freq_v; l++) { | |
| 81 | ✗ | for (int k = 0; k <= freq_h; k += 4) { | |
| 82 | ✗ | uint16_t offset = seed % 2048; | |
| 83 | ✗ | out[l][k + 0] = Gaussian_LUT[offset + 0]; | |
| 84 | ✗ | out[l][k + 1] = Gaussian_LUT[offset + 1]; | |
| 85 | ✗ | out[l][k + 2] = Gaussian_LUT[offset + 2]; | |
| 86 | ✗ | out[l][k + 3] = Gaussian_LUT[offset + 3]; | |
| 87 | ✗ | prng_shift(&seed); | |
| 88 | } | ||
| 89 | } | ||
| 90 | |||
| 91 | ✗ | out[0][0] = 0; | |
| 92 | |||
| 93 | // 64x64 inverse integer transform | ||
| 94 | ✗ | for (int y = 0; y < 64; y++) { | |
| 95 | ✗ | for (int x = 0; x <= freq_v; x++) { | |
| 96 | ✗ | int32_t sum = 0; | |
| 97 | ✗ | for (int p = 0; p <= freq_h; p++) | |
| 98 | ✗ | sum += R64T[y][p] * out[x][p]; | |
| 99 | ✗ | tmp[y][x] = (sum + 128) >> 8; | |
| 100 | } | ||
| 101 | } | ||
| 102 | |||
| 103 | ✗ | for (int y = 0; y < 64; y++) { | |
| 104 | ✗ | for (int x = 0; x < 64; x++) { | |
| 105 | ✗ | int32_t sum = 0; | |
| 106 | ✗ | for (int p = 0; p <= freq_v; p++) | |
| 107 | ✗ | sum += tmp[x][p] * R64T[y][p]; // R64T^T = R64 | |
| 108 | // Renormalize and clip to [-127, 127] | ||
| 109 | ✗ | out[y][x] = av_clip((sum + 128) >> 8, -127, 127); | |
| 110 | } | ||
| 111 | } | ||
| 112 | |||
| 113 | // Deblock horizontal edges by simple attenuation of values | ||
| 114 | ✗ | for (int y = 0; y < 64; y += 8) { | |
| 115 | ✗ | for (int x = 0; x < 64; x++) { | |
| 116 | ✗ | out[y + 0][x] = (out[y + 0][x] * deblock_coeff) >> 7; | |
| 117 | ✗ | out[y + 7][x] = (out[y + 7][x] * deblock_coeff) >> 7; | |
| 118 | } | ||
| 119 | } | ||
| 120 | ✗ | } | |
| 121 | |||
| 122 | ✗ | static void init_slice(uint8_t h, uint8_t v) | |
| 123 | { | ||
| 124 | static AVMutex mutex = AV_MUTEX_INITIALIZER; | ||
| 125 | ✗ | unsigned bitpos = h * 13 + v; | |
| 126 | ✗ | unsigned res = atomic_load_explicit(&film_grain_db.residency[bitpos / 32], | |
| 127 | memory_order_acquire); | ||
| 128 | |||
| 129 | ✗ | if (res & (1U << (bitpos & 31))) | |
| 130 | ✗ | return; | |
| 131 | |||
| 132 | ✗ | ff_mutex_lock(&mutex); | |
| 133 | ✗ | res = atomic_load_explicit(&film_grain_db.residency[bitpos / 32], memory_order_relaxed); | |
| 134 | ✗ | if (!(res & (1U << (bitpos & 31)))) { | |
| 135 | ✗ | init_slice_c(film_grain_db.db[h][v], h, v); | |
| 136 | ✗ | atomic_store_explicit(&film_grain_db.residency[bitpos / 32], | |
| 137 | res | (1U << (bitpos & 31)), memory_order_release); | ||
| 138 | } | ||
| 139 | ✗ | ff_mutex_unlock(&mutex); | |
| 140 | } | ||
| 141 | |||
| 142 | // Computes the average of an 8x8 block | ||
| 143 | ✗ | static uint16_t avg_8x8_c(const uint8_t *in, int in_stride) | |
| 144 | { | ||
| 145 | ✗ | uint16_t avg[8] = {0}; // summing over an array vectorizes better | |
| 146 | |||
| 147 | ✗ | for (int y = 0; y < 8; y++) { | |
| 148 | ✗ | for (int x = 0; x < 8; x++) | |
| 149 | ✗ | avg[x] += in[x]; | |
| 150 | ✗ | in += in_stride; | |
| 151 | } | ||
| 152 | |||
| 153 | ✗ | return (avg[0] + avg[1] + avg[2] + avg[3] + | |
| 154 | ✗ | avg[4] + avg[5] + avg[6] + avg[7]) >> 6; | |
| 155 | } | ||
| 156 | |||
| 157 | // Synthesize an 8x8 block of film grain by copying the pattern from `db` | ||
| 158 | ✗ | static void synth_grain_8x8_c(int8_t *out, const int out_stride, | |
| 159 | const int16_t scale, const uint8_t shift, | ||
| 160 | const int8_t *db) | ||
| 161 | { | ||
| 162 | ✗ | for (int y = 0; y < 8; y++) { | |
| 163 | ✗ | for (int x = 0; x < 8; x++) | |
| 164 | ✗ | out[x] = (scale * db[x]) >> shift; | |
| 165 | |||
| 166 | ✗ | out += out_stride; | |
| 167 | ✗ | db += 64; | |
| 168 | } | ||
| 169 | ✗ | } | |
| 170 | |||
| 171 | // Deblock vertical edges of an 8x8 block, mixing with the previous block | ||
| 172 | ✗ | static void deblock_8x8_c(int8_t *out, const int out_stride) | |
| 173 | { | ||
| 174 | ✗ | for (int y = 0; y < 8; y++) { | |
| 175 | ✗ | const int8_t l1 = out[-2], l0 = out[-1]; | |
| 176 | ✗ | const int8_t r0 = out[0], r1 = out[1]; | |
| 177 | ✗ | out[0] = (l0 + r0 * 2 + r1) >> 2; | |
| 178 | ✗ | out[-1] = (r0 + l0 * 2 + l1) >> 2; | |
| 179 | ✗ | out += out_stride; | |
| 180 | } | ||
| 181 | ✗ | } | |
| 182 | |||
| 183 | // Generates a single 8x8 block of grain, optionally also applying the | ||
| 184 | // deblocking step (note that this implies writing to the previous block). | ||
| 185 | ✗ | static av_always_inline void generate(int8_t *out, int out_stride, | |
| 186 | const uint8_t *in, int in_stride, | ||
| 187 | const AVFilmGrainH274Params *h274, | ||
| 188 | int c, int invert, int deblock, | ||
| 189 | int y_offset, int x_offset) | ||
| 190 | { | ||
| 191 | ✗ | const uint8_t shift = h274->log2_scale_factor + 6; | |
| 192 | ✗ | const uint16_t avg = avg_8x8_c(in, in_stride); | |
| 193 | int16_t scale; | ||
| 194 | uint8_t h, v; | ||
| 195 | ✗ | int8_t s = -1; | |
| 196 | |||
| 197 | // FIXME: This logic only generates grain with a single | ||
| 198 | // intensity interval. Strictly speaking, the H.274 specification allows | ||
| 199 | // for overlapping intensity intervals, however SMPTE RDD 5-2006 (which | ||
| 200 | // concerns the implementation of H.274 for H.264) forbids this as it | ||
| 201 | // requires a nontrivial grain synthesis process (FFT). | ||
| 202 | // | ||
| 203 | // In principle, we should detect this possibility ahead of time and warn | ||
| 204 | // the user that the output is unlikely to be correct, or alternatively | ||
| 205 | // return an AVERROR_PATCHWELCOME. | ||
| 206 | ✗ | for (int i = 0; i < h274->num_intensity_intervals[c]; i++) { | |
| 207 | ✗ | if (avg >= h274->intensity_interval_lower_bound[c][i] && | |
| 208 | ✗ | avg <= h274->intensity_interval_upper_bound[c][i]) | |
| 209 | { | ||
| 210 | ✗ | s = i; | |
| 211 | ✗ | break; | |
| 212 | } | ||
| 213 | } | ||
| 214 | |||
| 215 | ✗ | if (s < 0) { | |
| 216 | // No matching intensity interval, synthesize blank film grain | ||
| 217 | ✗ | for (int y = 0; y < 8; y++) | |
| 218 | ✗ | memset(out + y * out_stride, 0, sizeof(int8_t[8])); | |
| 219 | ✗ | return; | |
| 220 | } | ||
| 221 | |||
| 222 | ✗ | h = av_clip(h274->comp_model_value[c][s][1], 2, 14) - 2; | |
| 223 | ✗ | v = av_clip(h274->comp_model_value[c][s][2], 2, 14) - 2; | |
| 224 | ✗ | init_slice(h, v); | |
| 225 | |||
| 226 | ✗ | scale = h274->comp_model_value[c][s][0]; | |
| 227 | ✗ | if (invert) | |
| 228 | ✗ | scale = -scale; | |
| 229 | |||
| 230 | ✗ | synth_grain_8x8_c(out, out_stride, scale, shift, | |
| 231 | ✗ | &film_grain_db.db[h][v][y_offset][x_offset]); | |
| 232 | |||
| 233 | ✗ | if (deblock) | |
| 234 | ✗ | deblock_8x8_c(out, out_stride); | |
| 235 | } | ||
| 236 | |||
| 237 | // Saturating 8-bit sum of a+b | ||
| 238 | ✗ | static void add_8x8_clip_c(uint8_t *out, const uint8_t *a, const int8_t *b, | |
| 239 | int n) | ||
| 240 | { | ||
| 241 | ✗ | for (int i = 0; i < n; i++) | |
| 242 | ✗ | out[i] = av_clip_uint8(a[i] + b[i]); | |
| 243 | ✗ | } | |
| 244 | |||
| 245 | ✗ | int ff_h274_apply_film_grain(AVFrame *out_frame, const AVFrame *in_frame, | |
| 246 | const AVFilmGrainParams *params) | ||
| 247 | { | ||
| 248 | ✗ | AVFilmGrainH274Params h274 = params->codec.h274; | |
| 249 | av_assert1(params->type == AV_FILM_GRAIN_PARAMS_H274); | ||
| 250 | ✗ | if (h274.model_id != 0) | |
| 251 | ✗ | return AVERROR_PATCHWELCOME; | |
| 252 | |||
| 253 | av_assert1(out_frame->format == in_frame->format); | ||
| 254 | ✗ | if (in_frame->format != AV_PIX_FMT_YUV420P) | |
| 255 | ✗ | return AVERROR_PATCHWELCOME; | |
| 256 | |||
| 257 | ✗ | for (int c = 0; c < 3; c++) { | |
| 258 | static const uint8_t color_offset[3] = { 0, 85, 170 }; | ||
| 259 | ✗ | uint32_t seed = Seed_LUT[(params->seed + color_offset[c]) % 256]; | |
| 260 | ✗ | const int width = c > 0 ? AV_CEIL_RSHIFT(out_frame->width, 1) : out_frame->width; | |
| 261 | ✗ | const int height = c > 0 ? AV_CEIL_RSHIFT(out_frame->height, 1) : out_frame->height; | |
| 262 | |||
| 263 | ✗ | uint8_t * const out = out_frame->data[c]; | |
| 264 | ✗ | const int out_stride = out_frame->linesize[c]; | |
| 265 | ✗ | int8_t * const grain = out_frame->data[c]; // reuse output buffer for grain | |
| 266 | ✗ | const int grain_stride = out_stride; | |
| 267 | ✗ | const uint8_t * const in = in_frame->data[c]; | |
| 268 | ✗ | const int in_stride = in_frame->linesize[c]; | |
| 269 | |||
| 270 | ✗ | if (!h274.component_model_present[c]) { | |
| 271 | ✗ | av_image_copy_plane(out, out_stride, in, in_stride, | |
| 272 | width * sizeof(uint8_t), height); | ||
| 273 | ✗ | continue; | |
| 274 | } | ||
| 275 | |||
| 276 | ✗ | if (c > 0) { | |
| 277 | // Adaptation for 4:2:0 chroma subsampling | ||
| 278 | ✗ | for (int i = 0; i < h274.num_intensity_intervals[c]; i++) { | |
| 279 | ✗ | h274.comp_model_value[c][i][0] >>= 1; | |
| 280 | ✗ | h274.comp_model_value[c][i][1] *= 2; | |
| 281 | ✗ | h274.comp_model_value[c][i][2] *= 2; | |
| 282 | } | ||
| 283 | } | ||
| 284 | |||
| 285 | // Film grain synthesis is done in 8x8 blocks, but the PRNG state is | ||
| 286 | // only advanced in 16x16 blocks, so use a nested loop | ||
| 287 | ✗ | for (int y = 0; y < height; y += 16) { | |
| 288 | ✗ | for (int x = 0; x < width; x += 16) { | |
| 289 | ✗ | uint16_t x_offset = (seed >> 16) % 52; | |
| 290 | ✗ | uint16_t y_offset = (seed & 0xFFFF) % 56; | |
| 291 | ✗ | const int invert = (seed & 0x1); | |
| 292 | ✗ | x_offset &= 0xFFFC; | |
| 293 | ✗ | y_offset &= 0xFFF8; | |
| 294 | ✗ | prng_shift(&seed); | |
| 295 | |||
| 296 | ✗ | for (int yy = 0; yy < 16 && y+yy < height; yy += 8) { | |
| 297 | ✗ | for (int xx = 0; xx < 16 && x+xx < width; xx += 8) { | |
| 298 | ✗ | generate(grain + (y+yy) * grain_stride + (x+xx), grain_stride, | |
| 299 | ✗ | in + (y+yy) * in_stride + (x+xx), in_stride, | |
| 300 | ✗ | &h274, c, invert, (x+xx) > 0, | |
| 301 | y_offset + yy, x_offset + xx); | ||
| 302 | } | ||
| 303 | } | ||
| 304 | } | ||
| 305 | } | ||
| 306 | |||
| 307 | // Final output blend pass, done after grain synthesis is complete | ||
| 308 | // because deblocking depends on previous grain values | ||
| 309 | ✗ | for (int y = 0; y < height; y++) { | |
| 310 | ✗ | add_8x8_clip_c(out + y * out_stride, in + y * in_stride, | |
| 311 | ✗ | grain + y * grain_stride, width); | |
| 312 | } | ||
| 313 | } | ||
| 314 | |||
| 315 | ✗ | return 0; | |
| 316 | } | ||
| 317 | |||
| 318 | // These tables are all taken from the SMPTE RDD 5-2006 specification | ||
| 319 | static const int8_t Gaussian_LUT[2048+4] = { | ||
| 320 | -11, 12, 103, -11, 42, -35, 12, 59, 77, 98, -87, 3, 65, -78, 45, 56, -51, 21, | ||
| 321 | 13, -11, -20, -19, 33, -127, 17, -6, -105, 18, 19, 71, 48, -10, -38, 42, | ||
| 322 | -2, 75, -67, 52, -90, 33, -47, 21, -3, -56, 49, 1, -57, -42, -1, 120, -127, | ||
| 323 | -108, -49, 9, 14, 127, 122, 109, 52, 127, 2, 7, 114, 19, 30, 12, 77, 112, | ||
| 324 | 82, -61, -127, 111, -52, -29, 2, -49, -24, 58, -29, -73, 12, 112, 67, 79, | ||
| 325 | -3, -114, -87, -6, -5, 40, 58, -81, 49, -27, -31, -34, -105, 50, 16, -24, | ||
| 326 | -35, -14, -15, -127, -55, -22, -55, -127, -112, 5, -26, -72, 127, 127, -2, | ||
| 327 | 41, 87, -65, -16, 55, 19, 91, -81, -65, -64, 35, -7, -54, 99, -7, 88, 125, | ||
| 328 | -26, 91, 0, 63, 60, -14, -23, 113, -33, 116, 14, 26, 51, -16, 107, -8, 53, | ||
| 329 | 38, -34, 17, -7, 4, -91, 6, 63, 63, -15, 39, -36, 19, 55, 17, -51, 40, 33, | ||
| 330 | -37, 126, -39, -118, 17, -30, 0, 19, 98, 60, 101, -12, -73, -17, -52, 98, | ||
| 331 | 3, 3, 60, 33, -3, -2, 10, -42, -106, -38, 14, 127, 16, -127, -31, -86, -39, | ||
| 332 | -56, 46, -41, 75, 23, -19, -22, -70, 74, -54, -2, 32, -45, 17, -92, 59, | ||
| 333 | -64, -67, 56, -102, -29, -87, -34, -92, 68, 5, -74, -61, 93, -43, 14, -26, | ||
| 334 | -38, -126, -17, 16, -127, 64, 34, 31, 93, 17, -51, -59, 71, 77, 81, 127, | ||
| 335 | 127, 61, 33, -106, -93, 0, 0, 75, -69, 71, 127, -19, -111, 30, 23, 15, 2, | ||
| 336 | 39, 92, 5, 42, 2, -6, 38, 15, 114, -30, -37, 50, 44, 106, 27, 119, 7, -80, | ||
| 337 | 25, -68, -21, 92, -11, -1, 18, 41, -50, 79, -127, -43, 127, 18, 11, -21, | ||
| 338 | 32, -52, 27, -88, -90, -39, -19, -10, 24, -118, 72, -24, -44, 2, 12, 86, | ||
| 339 | -107, 39, -33, -127, 47, 51, -24, -22, 46, 0, 15, -35, -69, -2, -74, 24, | ||
| 340 | -6, 0, 29, -3, 45, 32, -32, 117, -45, 79, -24, -17, -109, -10, -70, 88, | ||
| 341 | -48, 24, -91, 120, -37, 50, -127, 58, 32, -82, -10, -17, -7, 46, -127, -15, | ||
| 342 | 89, 127, 17, 98, -39, -33, 37, 42, -40, -32, -21, 105, -19, 19, 19, -59, | ||
| 343 | -9, 30, 0, -127, 34, 127, -84, 75, 24, -40, -49, -127, -107, -14, 45, -75, | ||
| 344 | 1, 30, -20, 41, -68, -40, 12, 127, -3, 5, 20, -73, -59, -127, -3, -3, -53, | ||
| 345 | -6, -119, 93, 120, -80, -50, 0, 20, -46, 67, 78, -12, -22, -127, 36, -41, | ||
| 346 | 56, 119, -5, -116, -22, 68, -14, -90, 24, -82, -44, -127, 107, -25, -37, | ||
| 347 | 40, -7, -7, -82, 5, -87, 44, -34, 9, -127, 39, 70, 49, -63, 74, -49, 109, | ||
| 348 | -27, -89, -47, -39, 44, 49, -4, 60, -42, 80, 9, -127, -9, -56, -49, 125, | ||
| 349 | -66, 47, 36, 117, 15, -11, -96, 109, 94, -17, -56, 70, 8, -14, -5, 50, 37, | ||
| 350 | -45, 120, -30, -76, 40, -46, 6, 3, 69, 17, -78, 1, -79, 6, 127, 43, 26, | ||
| 351 | 127, -127, 28, -55, -26, 55, 112, 48, 107, -1, -77, -1, 53, -9, -22, -43, | ||
| 352 | 123, 108, 127, 102, 68, 46, 5, 1, 123, -13, -55, -34, -49, 89, 65, -105, | ||
| 353 | -5, 94, -53, 62, 45, 30, 46, 18, -35, 15, 41, 47, -98, -24, 94, -75, 127, | ||
| 354 | -114, 127, -68, 1, -17, 51, -95, 47, 12, 34, -45, -75, 89, -107, -9, -58, | ||
| 355 | -29, -109, -24, 127, -61, -13, 77, -45, 17, 19, 83, -24, 9, 127, -66, 54, | ||
| 356 | 4, 26, 13, 111, 43, -113, -22, 10, -24, 83, 67, -14, 75, -123, 59, 127, | ||
| 357 | -12, 99, -19, 64, -38, 54, 9, 7, 61, -56, 3, -57, 113, -104, -59, 3, -9, | ||
| 358 | -47, 74, 85, -55, -34, 12, 118, 28, 93, -72, 13, -99, -72, -20, 30, 72, | ||
| 359 | -94, 19, -54, 64, -12, -63, -25, 65, 72, -10, 127, 0, -127, 103, -20, -73, | ||
| 360 | -112, -103, -6, 28, -42, -21, -59, -29, -26, 19, -4, -51, 94, -58, -95, | ||
| 361 | -37, 35, 20, -69, 127, -19, -127, -22, -120, -53, 37, 74, -127, -1, -12, | ||
| 362 | -119, -53, -28, 38, 69, 17, 16, -114, 89, 62, 24, 37, -23, 49, -101, -32, | ||
| 363 | -9, -95, -53, 5, 93, -23, -49, -8, 51, 3, -75, -90, -10, -39, 127, -86, | ||
| 364 | -22, 20, 20, 113, 75, 52, -31, 92, -63, 7, -12, 46, 36, 101, -43, -17, -53, | ||
| 365 | -7, -38, -76, -31, -21, 62, 31, 62, 20, -127, 31, 64, 36, 102, -85, -10, | ||
| 366 | 77, 80, 58, -79, -8, 35, 8, 80, -24, -9, 3, -17, 72, 127, 83, -87, 55, 18, | ||
| 367 | -119, -123, 36, 10, 127, 56, -55, 113, 13, 26, 32, -13, -48, 22, -13, 5, | ||
| 368 | 58, 27, 24, 26, -11, -36, 37, -92, 78, 81, 9, 51, 14, 67, -13, 0, 32, 45, | ||
| 369 | -76, 32, -39, -22, -49, -127, -27, 31, -9, 36, 14, 71, 13, 57, 12, -53, | ||
| 370 | -86, 53, -44, -35, 2, 127, 12, -66, -44, 46, -115, 3, 10, 56, -35, 119, | ||
| 371 | -19, -61, 52, -59, -127, -49, -23, 4, -5, 17, -82, -6, 127, 25, 79, 67, 64, | ||
| 372 | -25, 14, -64, -37, -127, -28, 21, -63, 66, -53, -41, 109, -62, 15, -22, 13, | ||
| 373 | 29, -63, 20, 27, 95, -44, -59, -116, -10, 79, -49, 22, -43, -16, 46, -47, | ||
| 374 | -120, -36, -29, -52, -44, 29, 127, -13, 49, -9, -127, 75, -28, -23, 88, 59, | ||
| 375 | 11, -95, 81, -59, 58, 60, -26, 40, -92, -3, -22, -58, -45, -59, -22, -53, | ||
| 376 | 71, -29, 66, -32, -23, 14, -17, -66, -24, -28, -62, 47, 38, 17, 16, -37, | ||
| 377 | -24, -11, 8, -27, -19, 59, 45, -49, -47, -4, -22, -81, 30, -67, -127, 74, | ||
| 378 | 102, 5, -18, 98, 34, -66, 42, -52, 7, -59, 24, -58, -19, -24, -118, -73, | ||
| 379 | 91, 15, -16, 79, -32, -79, -127, -36, 41, 77, -83, 2, 56, 22, -75, 127, | ||
| 380 | -16, -21, 12, 31, 56, -113, -127, 90, 55, 61, 12, 55, -14, -113, -14, 32, | ||
| 381 | 49, -67, -17, 91, -10, 1, 21, 69, -70, 99, -19, -112, 66, -90, -10, -9, | ||
| 382 | -71, 127, 50, -81, -49, 24, 61, -61, -111, 7, -41, 127, 88, -66, 108, -127, | ||
| 383 | -6, 36, -14, 41, -50, 14, 14, 73, -101, -28, 77, 127, -8, -100, 88, 38, | ||
| 384 | 121, 88, -125, -60, 13, -94, -115, 20, -67, -87, -94, -119, 44, -28, -30, | ||
| 385 | 18, 5, -53, -61, 20, -43, 11, -77, -60, 13, 29, 3, 6, -72, 38, -60, -11, | ||
| 386 | 108, -53, 41, 66, -12, -127, -127, -49, 24, 29, 46, 36, 91, 34, -33, 116, | ||
| 387 | -51, -34, -52, 91, 7, -83, 73, -26, -103, 24, -10, 76, 84, 5, 68, -80, -13, | ||
| 388 | -17, -32, -48, 20, 50, 26, 10, 63, -104, -14, 37, 127, 114, 97, 35, 1, -33, | ||
| 389 | -55, 127, -124, -33, 61, -7, 119, -32, -127, -53, -42, 63, 3, -5, -26, 70, | ||
| 390 | -58, -33, -44, -43, 34, -56, -127, 127, 25, -35, -11, 16, -81, 29, -58, 40, | ||
| 391 | -127, -127, 20, -47, -11, -36, -63, -52, -32, -82, 78, -76, -73, 8, 27, | ||
| 392 | -72, -9, -74, -85, -86, -57, 25, 78, -10, -97, 35, -65, 8, -59, 14, 1, -42, | ||
| 393 | 32, -88, -44, 17, -3, -9, 59, 40, 12, -108, -40, 24, 34, 18, -28, 2, 51, | ||
| 394 | -110, -4, 100, 1, 65, 22, 0, 127, 61, 45, 25, -31, 6, 9, -7, -48, 99, 16, | ||
| 395 | 44, -2, -40, 32, -39, -52, 10, -110, -19, 56, -127, 69, 26, 51, 92, 40, 61, | ||
| 396 | -52, 45, -38, 13, 85, 122, 27, 66, 45, -111, -83, -3, 31, 37, 19, -36, 58, | ||
| 397 | 71, 39, -78, -47, 58, -78, 8, -62, -36, -14, 61, 42, -127, 71, -4, 24, -54, | ||
| 398 | 52, -127, 67, -4, -42, 30, -63, 59, -3, -1, -18, -46, -92, -81, -96, -14, | ||
| 399 | -53, -10, -11, -77, 13, 1, 8, -67, -127, 127, -28, 26, -14, 18, -13, -26, | ||
| 400 | 2, 10, -46, -32, -15, 27, -31, -59, 59, 77, -121, 28, 40, -54, -62, -31, | ||
| 401 | -21, -37, -32, -6, -127, -25, -60, 70, -127, 112, -127, 127, 88, -7, 116, | ||
| 402 | 110, 53, 87, -127, 3, 16, 23, 74, -106, -51, 3, 74, -82, -112, -74, 65, 81, | ||
| 403 | 25, 53, 127, -45, -50, -103, -41, -65, -29, 79, -67, 64, -33, -30, -8, 127, | ||
| 404 | 0, -13, -51, 67, -14, 5, -92, 29, -35, -8, -90, -57, -3, 36, 43, 44, -31, | ||
| 405 | -69, -7, 36, 39, -51, 43, -81, 58, 6, 127, 12, 57, 66, 46, 59, -43, -42, | ||
| 406 | 41, -15, -120, 24, 3, -11, 19, -13, 51, 28, 3, 55, -48, -12, -1, 2, 97, | ||
| 407 | -19, 29, 42, 13, 43, 78, -44, 56, -108, -43, -19, 127, 15, -11, -18, -81, | ||
| 408 | 83, -37, 77, -109, 15, 65, -50, 43, 12, 13, 27, 28, 61, 57, 30, 26, 106, | ||
| 409 | -18, 56, 13, 97, 4, -8, -62, -103, 94, 108, -44, 52, 27, -47, -9, 105, -53, | ||
| 410 | 46, 89, 103, -33, 38, -34, 55, 51, 70, -94, -35, -87, -107, -19, -31, 9, | ||
| 411 | -19, 79, -14, 77, 5, -19, -107, 85, 21, -45, -39, -42, 9, -29, 74, 47, -75, | ||
| 412 | 60, -127, 120, -112, -57, -32, 41, 7, 79, 76, 66, 57, 41, -25, 31, 37, -47, | ||
| 413 | -36, 43, -73, -37, 63, 127, -69, -52, 90, -33, -61, 60, -55, 44, 15, 4, | ||
| 414 | -67, 13, -92, 64, 29, -39, -3, 83, -2, -38, -85, -86, 58, 35, -69, -61, 29, | ||
| 415 | -37, -95, -78, 4, 30, -4, -32, -80, -22, -9, -77, 46, 7, -93, -71, 65, 9, | ||
| 416 | -50, 127, -70, 26, -12, -39, -114, 63, -127, -100, 4, -32, 111, 22, -60, | ||
| 417 | 65, -101, 26, -42, 21, -59, -27, -74, 2, -94, 6, 126, 5, 76, -88, -9, -43, | ||
| 418 | -101, 127, 1, 125, 92, -63, 52, 56, 4, 81, -127, 127, 80, 127, -29, 30, | ||
| 419 | 116, -74, -17, -57, 105, 48, 45, 25, -72, 48, -38, -108, 31, -34, 4, -11, | ||
| 420 | 41, -127, 52, -104, -43, -37, 52, 2, 47, 87, -9, 77, 27, -41, -25, 90, 86, | ||
| 421 | -56, 75, 10, 33, 78, 58, 127, 127, -7, -73, 49, -33, -106, -35, 38, 57, 53, | ||
| 422 | -17, -4, 83, 52, -108, 54, -125, 28, 23, 56, -43, -88, -17, -6, 47, 23, -9, | ||
| 423 | 0, -13, 111, 75, 27, -52, -38, -34, 39, 30, 66, 39, 38, -64, 38, 3, 21, | ||
| 424 | -32, -51, -28, 54, -38, -87, 20, 52, 115, 18, -81, -70, 0, -14, -46, -46, | ||
| 425 | -3, 125, 16, -14, 23, -82, -84, -69, -20, -65, -127, 9, 81, -49, 61, 7, | ||
| 426 | -36, -45, -42, 57, -26, 47, 20, -85, 46, -13, 41, -37, -75, -60, 86, -78, | ||
| 427 | -127, 12, 50, 2, -3, 13, 47, 5, 19, -78, -55, -27, 65, -71, 12, -108, 20, | ||
| 428 | -16, 11, -31, 63, -55, 37, 75, -17, 127, -73, -33, -28, -120, 105, 68, 106, | ||
| 429 | -103, -106, 71, 61, 2, 23, -3, 33, -5, -15, -67, -15, -23, -54, 15, -63, | ||
| 430 | 76, 58, -110, 1, 83, -27, 22, 75, -39, -17, -11, 64, -17, -127, -54, -66, | ||
| 431 | 31, 96, 116, 3, -114, -7, -108, -63, 97, 9, 50, 8, 75, -28, 72, 112, -36, | ||
| 432 | -112, 95, -50, 23, -13, -19, 55, 21, 23, 92, 91, 22, -49, 16, -75, 23, 9, | ||
| 433 | -49, -97, -37, 49, -36, 36, -127, -86, 43, 127, -24, -24, 84, 83, -35, -34, | ||
| 434 | -12, 109, 102, -38, 51, -68, 34, 19, -22, 49, -32, 127, 40, 24, -93, -4, | ||
| 435 | -3, 105, 3, -58, -18, 8, 127, -18, 125, 68, 69, -62, 30, -36, 54, -57, -24, | ||
| 436 | 17, 43, -36, -27, -57, -67, -21, -10, -49, 68, 12, 65, 4, 48, 55, 127, -75, | ||
| 437 | 44, 89, -66, -13, -78, -82, -91, 22, 30, 33, -40, -87, -34, 96, -91, 39, | ||
| 438 | 10, -64, -3, -12, 127, -50, -37, -56, 23, -35, -36, -54, 90, -91, 2, 50, | ||
| 439 | 77, -6, -127, 16, 46, -5, -73, 0, -56, -18, -72, 28, 93, 60, 49, 20, 18, | ||
| 440 | 111, -111, 32, -83, 47, 47, -10, 35, -88, 43, 57, -98, 127, -17, 0, 1, -39, | ||
| 441 | -127, -2, 0, 63, 93, 0, 36, -66, -61, -19, 39, -127, 58, 50, -17, 127, 88, | ||
| 442 | -43, -108, -51, -16, 7, -36, 68, 46, -14, 107, 40, 57, 7, 19, 8, 3, 88, | ||
| 443 | -90, -92, -18, -21, -24, 13, 7, -4, -78, -91, -4, 8, -35, -5, 19, 2, -111, | ||
| 444 | 4, -66, -81, 122, -20, -34, -37, -84, 127, 68, 46, 17, 47, | ||
| 445 | |||
| 446 | // Repeat the beginning of the array to allow wrapping reads | ||
| 447 | -11, 12, 103, -11, | ||
| 448 | }; | ||
| 449 | |||
| 450 | static const uint32_t Seed_LUT[256] = { | ||
| 451 | 747538460, 1088979410, 1744950180, 1767011913, 1403382928, | ||
| 452 | 521866116, 1060417601, 2110622736, 1557184770, 105289385, 585624216, | ||
| 453 | 1827676546, 1191843873, 1018104344, 1123590530, 663361569, 2023850500, | ||
| 454 | 76561770, 1226763489, 80325252, 1992581442, 502705249, 740409860, | ||
| 455 | 516219202, 557974537, 1883843076, 720112066, 1640137737, 1820967556, | ||
| 456 | 40667586, 155354121, 1820967557, 1115949072, 1631803309, 98284748, | ||
| 457 | 287433856, 2119719977, 988742797, 1827432592, 579378475, 1017745956, | ||
| 458 | 1309377032, 1316535465, 2074315269, 1923385360, 209722667, 1546228260, | ||
| 459 | 168102420, 135274561, 355958469, 248291472, 2127839491, 146920100, | ||
| 460 | 585982612, 1611702337, 696506029, 1386498192, 1258072451, 1212240548, | ||
| 461 | 1043171860, 1217404993, 1090770605, 1386498193, 169093201, 541098240, | ||
| 462 | 1468005469, 456510673, 1578687785, 1838217424, 2010752065, 2089828354, | ||
| 463 | 1362717428, 970073673, 854129835, 714793201, 1266069081, 1047060864, | ||
| 464 | 1991471829, 1098097741, 913883585, 1669598224, 1337918685, 1219264706, | ||
| 465 | 1799741108, 1834116681, 683417731, 1120274457, 1073098457, 1648396544, | ||
| 466 | 176642749, 31171789, 718317889, 1266977808, 1400892508, 549749008, | ||
| 467 | 1808010512, 67112961, 1005669825, 903663673, 1771104465, 1277749632, | ||
| 468 | 1229754427, 950632997, 1979371465, 2074373264, 305357524, 1049387408, | ||
| 469 | 1171033360, 1686114305, 2147468765, 1941195985, 117709841, 809550080, | ||
| 470 | 991480851, 1816248997, 1561503561, 329575568, 780651196, 1659144592, | ||
| 471 | 1910793616, 604016641, 1665084765, 1530186961, 1870928913, 809550081, | ||
| 472 | 2079346113, 71307521, 876663040, 1073807360, 832356664, 1573927377, | ||
| 473 | 204073344, 2026918147, 1702476788, 2043881033, 57949587, 2001393952, | ||
| 474 | 1197426649, 1186508931, 332056865, 950043140, 890043474, 349099312, | ||
| 475 | 148914948, 236204097, 2022643605, 1441981517, 498130129, 1443421481, | ||
| 476 | 924216797, 1817491777, 1913146664, 1411989632, 929068432, 495735097, | ||
| 477 | 1684636033, 1284520017, 432816184, 1344884865, 210843729, 676364544, | ||
| 478 | 234449232, 12112337, 1350619139, 1753272996, 2037118872, 1408560528, | ||
| 479 | 533334916, 1043640385, 357326099, 201376421, 110375493, 541106497, | ||
| 480 | 416159637, 242512193, 777294080, 1614872576, 1535546636, 870600145, | ||
| 481 | 910810409, 1821440209, 1605432464, 1145147393, 951695441, 1758494976, | ||
| 482 | 1506656568, 1557150160, 608221521, 1073840384, 217672017, 684818688, | ||
| 483 | 1750138880, 16777217, 677990609, 953274371, 1770050213, 1359128393, | ||
| 484 | 1797602707, 1984616737, 1865815816, 2120835200, 2051677060, 1772234061, | ||
| 485 | 1579794881, 1652821009, 1742099468, 1887260865, 46468113, 1011925248, | ||
| 486 | 1134107920, 881643832, 1354774993, 472508800, 1892499769, 1752793472, | ||
| 487 | 1962502272, 687898625, 883538000, 1354355153, 1761673473, 944820481, | ||
| 488 | 2020102353, 22020353, 961597696, 1342242816, 964808962, 1355809701, | ||
| 489 | 17016649, 1386540177, 647682692, 1849012289, 751668241, 1557184768, | ||
| 490 | 127374604, 1927564752, 1045744913, 1614921984, 43588881, 1016185088, | ||
| 491 | 1544617984, 1090519041, 136122424, 215038417, 1563027841, 2026918145, | ||
| 492 | 1688778833, 701530369, 1372639488, 1342242817, 2036945104, 953274369, | ||
| 493 | 1750192384, 16842753, 964808960, 1359020032, 1358954497 | ||
| 494 | }; | ||
| 495 | |||
| 496 | // Note: This is pre-transposed, i.e. stored column-major order | ||
| 497 | static const int8_t R64T[64][64] = { | ||
| 498 | { | ||
| 499 | 32, 45, 45, 45, 45, 45, 45, 45, 44, 44, 44, 44, 43, 43, 43, 42, | ||
| 500 | 42, 41, 41, 40, 40, 39, 39, 38, 38, 37, 36, 36, 35, 34, 34, 33, | ||
| 501 | 32, 31, 30, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, | ||
| 502 | 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 4, 3, 2, 1, | ||
| 503 | }, { | ||
| 504 | 32, 45, 45, 44, 43, 42, 41, 39, 38, 36, 34, 31, 29, 26, 23, 20, | ||
| 505 | 17, 14, 11, 8, 4, 1, -2, -6, -9, -12, -15, -18, -21, -24, -27, -30, | ||
| 506 | -32, -34, -36, -38, -40, -41, -43, -44, -44, -45, -45, -45, -45, -45, -44, -43, | ||
| 507 | -42, -40, -39, -37, -35, -33, -30, -28, -25, -22, -19, -16, -13, -10, -7, -3, | ||
| 508 | }, { | ||
| 509 | 32, 45, 44, 42, 40, 37, 34, 30, 25, 20, 15, 10, 4, -1, -7, -12, | ||
| 510 | -17, -22, -27, -31, -35, -38, -41, -43, -44, -45, -45, -45, -43, -41, -39, -36, | ||
| 511 | -32, -28, -23, -18, -13, -8, -2, 3, 9, 14, 19, 24, 29, 33, 36, 39, | ||
| 512 | 42, 44, 45, 45, 45, 44, 43, 40, 38, 34, 30, 26, 21, 16, 11, 6, | ||
| 513 | }, { | ||
| 514 | 32, 45, 43, 39, 35, 30, 23, 16, 9, 1, -7, -14, -21, -28, -34, -38, | ||
| 515 | -42, -44, -45, -45, -43, -40, -36, -31, -25, -18, -11, -3, 4, 12, 19, 26, | ||
| 516 | 32, 37, 41, 44, 45, 45, 44, 41, 38, 33, 27, 20, 13, 6, -2, -10, | ||
| 517 | -17, -24, -30, -36, -40, -43, -45, -45, -44, -42, -39, -34, -29, -22, -15, -8, | ||
| 518 | }, { | ||
| 519 | 32, 44, 41, 36, 29, 20, 11, 1, -9, -18, -27, -34, -40, -44, -45, -45, | ||
| 520 | -42, -37, -30, -22, -13, -3, 7, 16, 25, 33, 39, 43, 45, 45, 43, 38, | ||
| 521 | 32, 24, 15, 6, -4, -14, -23, -31, -38, -42, -45, -45, -43, -39, -34, -26, | ||
| 522 | -17, -8, 2, 12, 21, 30, 36, 41, 44, 45, 44, 40, 35, 28, 19, 10, | ||
| 523 | }, { | ||
| 524 | 32, 44, 39, 31, 21, 10, -2, -14, -25, -34, -41, -45, -45, -42, -36, -28, | ||
| 525 | -17, -6, 7, 18, 29, 37, 43, 45, 44, 40, 34, 24, 13, 1, -11, -22, | ||
| 526 | -32, -39, -44, -45, -43, -38, -30, -20, -9, 3, 15, 26, 35, 41, 45, 45, | ||
| 527 | 42, 36, 27, 16, 4, -8, -19, -30, -38, -43, -45, -44, -40, -33, -23, -12, | ||
| 528 | }, { | ||
| 529 | 32, 43, 36, 26, 13, -1, -15, -28, -38, -44, -45, -42, -35, -24, -11, 3, | ||
| 530 | 17, 30, 39, 44, 45, 41, 34, 22, 9, -6, -19, -31, -40, -45, -45, -40, | ||
| 531 | -32, -20, -7, 8, 21, 33, 41, 45, 44, 39, 30, 18, 4, -10, -23, -34, | ||
| 532 | -42, -45, -44, -38, -29, -16, -2, 12, 25, 36, 43, 45, 43, 37, 27, 14, | ||
| 533 | }, { | ||
| 534 | 32, 42, 34, 20, 4, -12, -27, -38, -44, -45, -39, -28, -13, 3, 19, 33, | ||
| 535 | 42, 45, 43, 34, 21, 6, -11, -26, -38, -44, -45, -39, -29, -14, 2, 18, | ||
| 536 | 32, 41, 45, 43, 35, 22, 7, -10, -25, -37, -44, -45, -40, -30, -15, 1, | ||
| 537 | 17, 31, 41, 45, 43, 36, 23, 8, -9, -24, -36, -44, -45, -40, -30, -16, | ||
| 538 | }, { | ||
| 539 | 32, 41, 30, 14, -4, -22, -36, -44, -44, -37, -23, -6, 13, 30, 41, 45, | ||
| 540 | 42, 31, 15, -3, -21, -36, -44, -45, -38, -24, -7, 12, 29, 40, 45, 42, | ||
| 541 | 32, 16, -2, -20, -35, -44, -45, -38, -25, -8, 11, 28, 40, 45, 43, 33, | ||
| 542 | 17, -1, -19, -34, -43, -45, -39, -26, -9, 10, 27, 39, 45, 43, 34, 18, | ||
| 543 | }, { | ||
| 544 | 32, 40, 27, 8, -13, -31, -43, -45, -38, -22, -2, 18, 35, 44, 44, 34, | ||
| 545 | 17, -3, -23, -38, -45, -42, -30, -12, 9, 28, 41, 45, 40, 26, 7, -14, | ||
| 546 | -32, -43, -45, -37, -21, -1, 19, 36, 44, 44, 34, 16, -4, -24, -39, -45, | ||
| 547 | -42, -30, -11, 10, 29, 41, 45, 39, 25, 6, -15, -33, -43, -45, -36, -20, | ||
| 548 | }, { | ||
| 549 | 32, 39, 23, 1, -21, -38, -45, -40, -25, -3, 19, 37, 45, 41, 27, 6, | ||
| 550 | -17, -36, -45, -42, -29, -8, 15, 34, 44, 43, 30, 10, -13, -33, -44, -44, | ||
| 551 | -32, -12, 11, 31, 43, 44, 34, 14, -9, -30, -43, -45, -35, -16, 7, 28, | ||
| 552 | 42, 45, 36, 18, -4, -26, -41, -45, -38, -20, 2, 24, 40, 45, 39, 22, | ||
| 553 | }, { | ||
| 554 | 32, 38, 19, -6, -29, -43, -44, -31, -9, 16, 36, 45, 40, 22, -2, -26, | ||
| 555 | -42, -45, -34, -12, 13, 34, 45, 41, 25, 1, -23, -40, -45, -36, -15, 10, | ||
| 556 | 32, 44, 43, 28, 4, -20, -39, -45, -38, -18, 7, 30, 43, 44, 30, 8, | ||
| 557 | -17, -37, -45, -39, -21, 3, 27, 42, 44, 33, 11, -14, -35, -45, -41, -24, | ||
| 558 | }, { | ||
| 559 | 32, 37, 15, -12, -35, -45, -39, -18, 9, 33, 45, 40, 21, -6, -30, -44, | ||
| 560 | -42, -24, 2, 28, 43, 43, 27, 1, -25, -42, -44, -30, -4, 22, 41, 45, | ||
| 561 | 32, 8, -19, -39, -45, -34, -11, 16, 38, 45, 36, 14, -13, -36, -45, -38, | ||
| 562 | -17, 10, 34, 45, 40, 20, -7, -31, -44, -41, -23, 3, 29, 44, 43, 26, | ||
| 563 | }, { | ||
| 564 | 32, 36, 11, -18, -40, -45, -30, -3, 25, 43, 43, 24, -4, -31, -45, -39, | ||
| 565 | -17, 12, 36, 45, 35, 10, -19, -40, -44, -30, -2, 26, 43, 42, 23, -6, | ||
| 566 | -32, -45, -39, -16, 13, 37, 45, 34, 9, -20, -41, -44, -29, -1, 27, 44, | ||
| 567 | 42, 22, -7, -33, -45, -38, -15, 14, 38, 45, 34, 8, -21, -41, -44, -28, | ||
| 568 | }, { | ||
| 569 | 32, 34, 7, -24, -43, -41, -19, 12, 38, 45, 30, 1, -29, -45, -39, -14, | ||
| 570 | 17, 40, 44, 26, -4, -33, -45, -36, -9, 22, 43, 42, 21, -10, -36, -45, | ||
| 571 | -32, -3, 27, 44, 40, 16, -15, -39, -44, -28, 2, 31, 45, 37, 11, -20, | ||
| 572 | -42, -43, -23, 8, 35, 45, 34, 6, -25, -44, -41, -18, 13, 38, 45, 30, | ||
| 573 | }, { | ||
| 574 | 32, 33, 2, -30, -45, -36, -7, 26, 44, 38, 11, -22, -43, -40, -15, 18, | ||
| 575 | 42, 42, 19, -14, -40, -44, -23, 10, 38, 45, 27, -6, -35, -45, -30, 1, | ||
| 576 | 32, 45, 34, 3, -29, -45, -36, -8, 25, 44, 39, 12, -21, -43, -41, -16, | ||
| 577 | 17, 41, 43, 20, -13, -39, -44, -24, 9, 37, 45, 28, -4, -34, -45, -31, | ||
| 578 | }, { | ||
| 579 | 32, 31, -2, -34, -45, -28, 7, 37, 44, 24, -11, -39, -43, -20, 15, 41, | ||
| 580 | 42, 16, -19, -43, -40, -12, 23, 44, 38, 8, -27, -45, -35, -3, 30, 45, | ||
| 581 | 32, -1, -34, -45, -29, 6, 36, 45, 25, -10, -39, -44, -21, 14, 41, 42, | ||
| 582 | 17, -18, -43, -40, -13, 22, 44, 38, 9, -26, -45, -36, -4, 30, 45, 33, | ||
| 583 | }, { | ||
| 584 | 32, 30, -7, -38, -43, -18, 19, 44, 38, 6, -30, -45, -29, 8, 39, 43, | ||
| 585 | 17, -20, -44, -37, -4, 31, 45, 28, -9, -39, -43, -16, 21, 44, 36, 3, | ||
| 586 | -32, -45, -27, 10, 40, 42, 15, -22, -44, -36, -2, 33, 45, 26, -11, -40, | ||
| 587 | -42, -14, 23, 45, 35, 1, -34, -45, -25, 12, 41, 41, 13, -24, -45, -34, | ||
| 588 | }, { | ||
| 589 | 32, 28, -11, -41, -40, -8, 30, 45, 25, -14, -43, -38, -4, 33, 45, 22, | ||
| 590 | -17, -44, -36, -1, 35, 44, 19, -20, -44, -34, 2, 37, 43, 16, -23, -45, | ||
| 591 | -32, 6, 39, 42, 13, -26, -45, -30, 9, 40, 41, 10, -29, -45, -27, 12, | ||
| 592 | 42, 39, 7, -31, -45, -24, 15, 43, 38, 3, -34, -45, -21, 18, 44, 36, | ||
| 593 | }, { | ||
| 594 | 32, 26, -15, -44, -35, 3, 39, 41, 9, -31, -45, -20, 21, 45, 30, -10, | ||
| 595 | -42, -38, -2, 36, 43, 14, -27, -45, -25, 16, 44, 34, -4, -39, -41, -8, | ||
| 596 | 32, 45, 19, -22, -45, -30, 11, 42, 38, 1, -36, -43, -13, 28, 45, 24, | ||
| 597 | -17, -44, -34, 6, 40, 40, 7, -33, -44, -18, 23, 45, 29, -12, -43, -37, | ||
| 598 | }, { | ||
| 599 | 32, 24, -19, -45, -29, 14, 44, 33, -9, -42, -36, 3, 40, 39, 2, -37, | ||
| 600 | -42, -8, 34, 44, 13, -30, -45, -18, 25, 45, 23, -20, -45, -28, 15, 44, | ||
| 601 | 32, -10, -43, -36, 4, 40, 39, 1, -38, -41, -7, 34, 43, 12, -30, -45, | ||
| 602 | -17, 26, 45, 22, -21, -45, -27, 16, 44, 31, -11, -43, -35, 6, 41, 38, | ||
| 603 | }, { | ||
| 604 | 32, 22, -23, -45, -21, 24, 45, 20, -25, -45, -19, 26, 45, 18, -27, -45, | ||
| 605 | -17, 28, 45, 16, -29, -45, -15, 30, 44, 14, -30, -44, -13, 31, 44, 12, | ||
| 606 | -32, -44, -11, 33, 43, 10, -34, -43, -9, 34, 43, 8, -35, -42, -7, 36, | ||
| 607 | 42, 6, -36, -41, -4, 37, 41, 3, -38, -40, -2, 38, 40, 1, -39, -39, | ||
| 608 | }, { | ||
| 609 | 32, 20, -27, -45, -13, 33, 43, 6, -38, -39, 2, 41, 35, -10, -44, -30, | ||
| 610 | 17, 45, 23, -24, -45, -16, 30, 44, 9, -36, -41, -1, 40, 37, -7, -43, | ||
| 611 | -32, 14, 45, 26, -21, -45, -19, 28, 44, 12, -34, -42, -4, 38, 39, -3, | ||
| 612 | -42, -34, 11, 44, 29, -18, -45, -22, 25, 45, 15, -31, -43, -8, 36, 40, | ||
| 613 | }, { | ||
| 614 | 32, 18, -30, -43, -4, 39, 36, -10, -44, -26, 23, 45, 13, -34, -41, 1, | ||
| 615 | 42, 33, -15, -45, -21, 28, 44, 8, -38, -38, 7, 44, 29, -20, -45, -16, | ||
| 616 | 32, 42, 2, -40, -35, 12, 45, 24, -25, -45, -11, 36, 40, -3, -43, -31, | ||
| 617 | 17, 45, 19, -30, -43, -6, 39, 37, -9, -44, -27, 22, 45, 14, -34, -41, | ||
| 618 | }, { | ||
| 619 | 32, 16, -34, -40, 4, 44, 27, -24, -44, -8, 39, 36, -13, -45, -19, 31, | ||
| 620 | 42, -1, -43, -30, 21, 45, 11, -37, -38, 10, 45, 22, -29, -43, -2, 41, | ||
| 621 | 32, -18, -45, -14, 35, 39, -7, -44, -25, 26, 44, 6, -40, -34, 15, 45, | ||
| 622 | 17, -33, -41, 3, 43, 28, -23, -45, -9, 38, 36, -12, -45, -20, 30, 42, | ||
| 623 | }, { | ||
| 624 | 32, 14, -36, -37, 13, 45, 15, -36, -38, 12, 45, 16, -35, -38, 11, 45, | ||
| 625 | 17, -34, -39, 10, 45, 18, -34, -39, 9, 45, 19, -33, -40, 8, 45, 20, | ||
| 626 | -32, -40, 7, 45, 21, -31, -41, 6, 44, 22, -30, -41, 4, 44, 23, -30, | ||
| 627 | -42, 3, 44, 24, -29, -42, 2, 44, 25, -28, -43, 1, 43, 26, -27, -43, | ||
| 628 | }, { | ||
| 629 | 32, 12, -39, -33, 21, 44, 2, -43, -25, 30, 41, -8, -45, -16, 36, 36, | ||
| 630 | -17, -45, -7, 41, 29, -26, -43, 3, 44, 20, -34, -38, 13, 45, 11, -39, | ||
| 631 | -32, 22, 44, 1, -43, -24, 30, 40, -9, -45, -15, 37, 35, -18, -45, -6, | ||
| 632 | 42, 28, -27, -42, 4, 45, 19, -34, -38, 14, 45, 10, -40, -31, 23, 44, | ||
| 633 | }, { | ||
| 634 | 32, 10, -41, -28, 29, 40, -11, -45, -9, 41, 27, -30, -40, 12, 45, 8, | ||
| 635 | -42, -26, 30, 39, -13, -45, -7, 42, 25, -31, -39, 14, 45, 6, -43, -24, | ||
| 636 | 32, 38, -15, -45, -4, 43, 23, -33, -38, 16, 45, 3, -43, -22, 34, 37, | ||
| 637 | -17, -45, -2, 44, 21, -34, -36, 18, 44, 1, -44, -20, 35, 36, -19, -44, | ||
| 638 | }, { | ||
| 639 | 32, 8, -43, -22, 35, 34, -23, -42, 9, 45, 7, -43, -21, 36, 34, -24, | ||
| 640 | -42, 10, 45, 6, -43, -20, 36, 33, -25, -41, 11, 45, 4, -44, -19, 37, | ||
| 641 | 32, -26, -41, 12, 45, 3, -44, -18, 38, 31, -27, -40, 13, 45, 2, -44, | ||
| 642 | -17, 38, 30, -28, -40, 14, 45, 1, -44, -16, 39, 30, -29, -39, 15, 45, | ||
| 643 | }, { | ||
| 644 | 32, 6, -44, -16, 40, 26, -34, -34, 25, 40, -15, -44, 4, 45, 7, -44, | ||
| 645 | -17, 39, 27, -33, -35, 24, 41, -14, -44, 3, 45, 8, -43, -18, 39, 28, | ||
| 646 | -32, -36, 23, 41, -13, -45, 2, 45, 9, -43, -19, 38, 29, -31, -36, 22, | ||
| 647 | 42, -12, -45, 1, 45, 10, -43, -20, 38, 30, -30, -37, 21, 42, -11, -45, | ||
| 648 | }, { | ||
| 649 | 32, 3, -45, -10, 43, 16, -41, -22, 38, 28, -34, -33, 29, 37, -23, -40, | ||
| 650 | 17, 43, -11, -45, 4, 45, 2, -45, -9, 44, 15, -41, -21, 38, 27, -34, | ||
| 651 | -32, 30, 36, -24, -40, 18, 43, -12, -44, 6, 45, 1, -45, -8, 44, 14, | ||
| 652 | -42, -20, 39, 26, -35, -31, 30, 36, -25, -39, 19, 42, -13, -44, 7, 45, | ||
| 653 | }, { | ||
| 654 | 32, 1, -45, -3, 45, 6, -45, -8, 44, 10, -44, -12, 43, 14, -43, -16, | ||
| 655 | 42, 18, -41, -20, 40, 22, -39, -24, 38, 26, -36, -28, 35, 30, -34, -31, | ||
| 656 | 32, 33, -30, -34, 29, 36, -27, -37, 25, 38, -23, -39, 21, 40, -19, -41, | ||
| 657 | 17, 42, -15, -43, 13, 44, -11, -44, 9, 45, -7, -45, 4, 45, -2, -45, | ||
| 658 | }, { | ||
| 659 | 32, -1, -45, 3, 45, -6, -45, 8, 44, -10, -44, 12, 43, -14, -43, 16, | ||
| 660 | 42, -18, -41, 20, 40, -22, -39, 24, 38, -26, -36, 28, 35, -30, -34, 31, | ||
| 661 | 32, -33, -30, 34, 29, -36, -27, 37, 25, -38, -23, 39, 21, -40, -19, 41, | ||
| 662 | 17, -42, -15, 43, 13, -44, -11, 44, 9, -45, -7, 45, 4, -45, -2, 45, | ||
| 663 | }, { | ||
| 664 | 32, -3, -45, 10, 43, -16, -41, 22, 38, -28, -34, 33, 29, -37, -23, 40, | ||
| 665 | 17, -43, -11, 45, 4, -45, 2, 45, -9, -44, 15, 41, -21, -38, 27, 34, | ||
| 666 | -32, -30, 36, 24, -40, -18, 43, 12, -44, -6, 45, -1, -45, 8, 44, -14, | ||
| 667 | -42, 20, 39, -26, -35, 31, 30, -36, -25, 39, 19, -42, -13, 44, 7, -45, | ||
| 668 | }, { | ||
| 669 | 32, -6, -44, 16, 40, -26, -34, 34, 25, -40, -15, 44, 4, -45, 7, 44, | ||
| 670 | -17, -39, 27, 33, -35, -24, 41, 14, -44, -3, 45, -8, -43, 18, 39, -28, | ||
| 671 | -32, 36, 23, -41, -13, 45, 2, -45, 9, 43, -19, -38, 29, 31, -36, -22, | ||
| 672 | 42, 12, -45, -1, 45, -10, -43, 20, 38, -30, -30, 37, 21, -42, -11, 45, | ||
| 673 | }, { | ||
| 674 | 32, -8, -43, 22, 35, -34, -23, 42, 9, -45, 7, 43, -21, -36, 34, 24, | ||
| 675 | -42, -10, 45, -6, -43, 20, 36, -33, -25, 41, 11, -45, 4, 44, -19, -37, | ||
| 676 | 32, 26, -41, -12, 45, -3, -44, 18, 38, -31, -27, 40, 13, -45, 2, 44, | ||
| 677 | -17, -38, 30, 28, -40, -14, 45, -1, -44, 16, 39, -30, -29, 39, 15, -45, | ||
| 678 | }, { | ||
| 679 | 32, -10, -41, 28, 29, -40, -11, 45, -9, -41, 27, 30, -40, -12, 45, -8, | ||
| 680 | -42, 26, 30, -39, -13, 45, -7, -42, 25, 31, -39, -14, 45, -6, -43, 24, | ||
| 681 | 32, -38, -15, 45, -4, -43, 23, 33, -38, -16, 45, -3, -43, 22, 34, -37, | ||
| 682 | -17, 45, -2, -44, 21, 34, -36, -18, 44, -1, -44, 20, 35, -36, -19, 44, | ||
| 683 | }, { | ||
| 684 | 32, -12, -39, 33, 21, -44, 2, 43, -25, -30, 41, 8, -45, 16, 36, -36, | ||
| 685 | -17, 45, -7, -41, 29, 26, -43, -3, 44, -20, -34, 38, 13, -45, 11, 39, | ||
| 686 | -32, -22, 44, -1, -43, 24, 30, -40, -9, 45, -15, -37, 35, 18, -45, 6, | ||
| 687 | 42, -28, -27, 42, 4, -45, 19, 34, -38, -14, 45, -10, -40, 31, 23, -44, | ||
| 688 | }, { | ||
| 689 | 32, -14, -36, 37, 13, -45, 15, 36, -38, -12, 45, -16, -35, 38, 11, -45, | ||
| 690 | 17, 34, -39, -10, 45, -18, -34, 39, 9, -45, 19, 33, -40, -8, 45, -20, | ||
| 691 | -32, 40, 7, -45, 21, 31, -41, -6, 44, -22, -30, 41, 4, -44, 23, 30, | ||
| 692 | -42, -3, 44, -24, -29, 42, 2, -44, 25, 28, -43, -1, 43, -26, -27, 43, | ||
| 693 | }, { | ||
| 694 | 32, -16, -34, 40, 4, -44, 27, 24, -44, 8, 39, -36, -13, 45, -19, -31, | ||
| 695 | 42, 1, -43, 30, 21, -45, 11, 37, -38, -10, 45, -22, -29, 43, -2, -41, | ||
| 696 | 32, 18, -45, 14, 35, -39, -7, 44, -25, -26, 44, -6, -40, 34, 15, -45, | ||
| 697 | 17, 33, -41, -3, 43, -28, -23, 45, -9, -38, 36, 12, -45, 20, 30, -42, | ||
| 698 | }, { | ||
| 699 | 32, -18, -30, 43, -4, -39, 36, 10, -44, 26, 23, -45, 13, 34, -41, -1, | ||
| 700 | 42, -33, -15, 45, -21, -28, 44, -8, -38, 38, 7, -44, 29, 20, -45, 16, | ||
| 701 | 32, -42, 2, 40, -35, -12, 45, -24, -25, 45, -11, -36, 40, 3, -43, 31, | ||
| 702 | 17, -45, 19, 30, -43, 6, 39, -37, -9, 44, -27, -22, 45, -14, -34, 41, | ||
| 703 | }, { | ||
| 704 | 32, -20, -27, 45, -13, -33, 43, -6, -38, 39, 2, -41, 35, 10, -44, 30, | ||
| 705 | 17, -45, 23, 24, -45, 16, 30, -44, 9, 36, -41, 1, 40, -37, -7, 43, | ||
| 706 | -32, -14, 45, -26, -21, 45, -19, -28, 44, -12, -34, 42, -4, -38, 39, 3, | ||
| 707 | -42, 34, 11, -44, 29, 18, -45, 22, 25, -45, 15, 31, -43, 8, 36, -40, | ||
| 708 | }, { | ||
| 709 | 32, -22, -23, 45, -21, -24, 45, -20, -25, 45, -19, -26, 45, -18, -27, 45, | ||
| 710 | -17, -28, 45, -16, -29, 45, -15, -30, 44, -14, -30, 44, -13, -31, 44, -12, | ||
| 711 | -32, 44, -11, -33, 43, -10, -34, 43, -9, -34, 43, -8, -35, 42, -7, -36, | ||
| 712 | 42, -6, -36, 41, -4, -37, 41, -3, -38, 40, -2, -38, 40, -1, -39, 39, | ||
| 713 | }, { | ||
| 714 | 32, -24, -19, 45, -29, -14, 44, -33, -9, 42, -36, -3, 40, -39, 2, 37, | ||
| 715 | -42, 8, 34, -44, 13, 30, -45, 18, 25, -45, 23, 20, -45, 28, 15, -44, | ||
| 716 | 32, 10, -43, 36, 4, -40, 39, -1, -38, 41, -7, -34, 43, -12, -30, 45, | ||
| 717 | -17, -26, 45, -22, -21, 45, -27, -16, 44, -31, -11, 43, -35, -6, 41, -38, | ||
| 718 | }, { | ||
| 719 | 32, -26, -15, 44, -35, -3, 39, -41, 9, 31, -45, 20, 21, -45, 30, 10, | ||
| 720 | -42, 38, -2, -36, 43, -14, -27, 45, -25, -16, 44, -34, -4, 39, -41, 8, | ||
| 721 | 32, -45, 19, 22, -45, 30, 11, -42, 38, -1, -36, 43, -13, -28, 45, -24, | ||
| 722 | -17, 44, -34, -6, 40, -40, 7, 33, -44, 18, 23, -45, 29, 12, -43, 37, | ||
| 723 | }, { | ||
| 724 | 32, -28, -11, 41, -40, 8, 30, -45, 25, 14, -43, 38, -4, -33, 45, -22, | ||
| 725 | -17, 44, -36, 1, 35, -44, 19, 20, -44, 34, 2, -37, 43, -16, -23, 45, | ||
| 726 | -32, -6, 39, -42, 13, 26, -45, 30, 9, -40, 41, -10, -29, 45, -27, -12, | ||
| 727 | 42, -39, 7, 31, -45, 24, 15, -43, 38, -3, -34, 45, -21, -18, 44, -36, | ||
| 728 | }, { | ||
| 729 | 32, -30, -7, 38, -43, 18, 19, -44, 38, -6, -30, 45, -29, -8, 39, -43, | ||
| 730 | 17, 20, -44, 37, -4, -31, 45, -28, -9, 39, -43, 16, 21, -44, 36, -3, | ||
| 731 | -32, 45, -27, -10, 40, -42, 15, 22, -44, 36, -2, -33, 45, -26, -11, 40, | ||
| 732 | -42, 14, 23, -45, 35, -1, -34, 45, -25, -12, 41, -41, 13, 24, -45, 34, | ||
| 733 | }, { | ||
| 734 | 32, -31, -2, 34, -45, 28, 7, -37, 44, -24, -11, 39, -43, 20, 15, -41, | ||
| 735 | 42, -16, -19, 43, -40, 12, 23, -44, 38, -8, -27, 45, -35, 3, 30, -45, | ||
| 736 | 32, 1, -34, 45, -29, -6, 36, -45, 25, 10, -39, 44, -21, -14, 41, -42, | ||
| 737 | 17, 18, -43, 40, -13, -22, 44, -38, 9, 26, -45, 36, -4, -30, 45, -33, | ||
| 738 | }, { | ||
| 739 | 32, -33, 2, 30, -45, 36, -7, -26, 44, -38, 11, 22, -43, 40, -15, -18, | ||
| 740 | 42, -42, 19, 14, -40, 44, -23, -10, 38, -45, 27, 6, -35, 45, -30, -1, | ||
| 741 | 32, -45, 34, -3, -29, 45, -36, 8, 25, -44, 39, -12, -21, 43, -41, 16, | ||
| 742 | 17, -41, 43, -20, -13, 39, -44, 24, 9, -37, 45, -28, -4, 34, -45, 31, | ||
| 743 | }, { | ||
| 744 | 32, -34, 7, 24, -43, 41, -19, -12, 38, -45, 30, -1, -29, 45, -39, 14, | ||
| 745 | 17, -40, 44, -26, -4, 33, -45, 36, -9, -22, 43, -42, 21, 10, -36, 45, | ||
| 746 | -32, 3, 27, -44, 40, -16, -15, 39, -44, 28, 2, -31, 45, -37, 11, 20, | ||
| 747 | -42, 43, -23, -8, 35, -45, 34, -6, -25, 44, -41, 18, 13, -38, 45, -30, | ||
| 748 | }, { | ||
| 749 | 32, -36, 11, 18, -40, 45, -30, 3, 25, -43, 43, -24, -4, 31, -45, 39, | ||
| 750 | -17, -12, 36, -45, 35, -10, -19, 40, -44, 30, -2, -26, 43, -42, 23, 6, | ||
| 751 | -32, 45, -39, 16, 13, -37, 45, -34, 9, 20, -41, 44, -29, 1, 27, -44, | ||
| 752 | 42, -22, -7, 33, -45, 38, -15, -14, 38, -45, 34, -8, -21, 41, -44, 28, | ||
| 753 | }, { | ||
| 754 | 32, -37, 15, 12, -35, 45, -39, 18, 9, -33, 45, -40, 21, 6, -30, 44, | ||
| 755 | -42, 24, 2, -28, 43, -43, 27, -1, -25, 42, -44, 30, -4, -22, 41, -45, | ||
| 756 | 32, -8, -19, 39, -45, 34, -11, -16, 38, -45, 36, -14, -13, 36, -45, 38, | ||
| 757 | -17, -10, 34, -45, 40, -20, -7, 31, -44, 41, -23, -3, 29, -44, 43, -26, | ||
| 758 | }, { | ||
| 759 | 32, -38, 19, 6, -29, 43, -44, 31, -9, -16, 36, -45, 40, -22, -2, 26, | ||
| 760 | -42, 45, -34, 12, 13, -34, 45, -41, 25, -1, -23, 40, -45, 36, -15, -10, | ||
| 761 | 32, -44, 43, -28, 4, 20, -39, 45, -38, 18, 7, -30, 43, -44, 30, -8, | ||
| 762 | -17, 37, -45, 39, -21, -3, 27, -42, 44, -33, 11, 14, -35, 45, -41, 24, | ||
| 763 | }, { | ||
| 764 | 32, -39, 23, -1, -21, 38, -45, 40, -25, 3, 19, -37, 45, -41, 27, -6, | ||
| 765 | -17, 36, -45, 42, -29, 8, 15, -34, 44, -43, 30, -10, -13, 33, -44, 44, | ||
| 766 | -32, 12, 11, -31, 43, -44, 34, -14, -9, 30, -43, 45, -35, 16, 7, -28, | ||
| 767 | 42, -45, 36, -18, -4, 26, -41, 45, -38, 20, 2, -24, 40, -45, 39, -22, | ||
| 768 | }, { | ||
| 769 | 32, -40, 27, -8, -13, 31, -43, 45, -38, 22, -2, -18, 35, -44, 44, -34, | ||
| 770 | 17, 3, -23, 38, -45, 42, -30, 12, 9, -28, 41, -45, 40, -26, 7, 14, | ||
| 771 | -32, 43, -45, 37, -21, 1, 19, -36, 44, -44, 34, -16, -4, 24, -39, 45, | ||
| 772 | -42, 30, -11, -10, 29, -41, 45, -39, 25, -6, -15, 33, -43, 45, -36, 20, | ||
| 773 | }, { | ||
| 774 | 32, -41, 30, -14, -4, 22, -36, 44, -44, 37, -23, 6, 13, -30, 41, -45, | ||
| 775 | 42, -31, 15, 3, -21, 36, -44, 45, -38, 24, -7, -12, 29, -40, 45, -42, | ||
| 776 | 32, -16, -2, 20, -35, 44, -45, 38, -25, 8, 11, -28, 40, -45, 43, -33, | ||
| 777 | 17, 1, -19, 34, -43, 45, -39, 26, -9, -10, 27, -39, 45, -43, 34, -18, | ||
| 778 | }, { | ||
| 779 | 32, -42, 34, -20, 4, 12, -27, 38, -44, 45, -39, 28, -13, -3, 19, -33, | ||
| 780 | 42, -45, 43, -34, 21, -6, -11, 26, -38, 44, -45, 39, -29, 14, 2, -18, | ||
| 781 | 32, -41, 45, -43, 35, -22, 7, 10, -25, 37, -44, 45, -40, 30, -15, -1, | ||
| 782 | 17, -31, 41, -45, 43, -36, 23, -8, -9, 24, -36, 44, -45, 40, -30, 16, | ||
| 783 | }, { | ||
| 784 | 32, -43, 36, -26, 13, 1, -15, 28, -38, 44, -45, 42, -35, 24, -11, -3, | ||
| 785 | 17, -30, 39, -44, 45, -41, 34, -22, 9, 6, -19, 31, -40, 45, -45, 40, | ||
| 786 | -32, 20, -7, -8, 21, -33, 41, -45, 44, -39, 30, -18, 4, 10, -23, 34, | ||
| 787 | -42, 45, -44, 38, -29, 16, -2, -12, 25, -36, 43, -45, 43, -37, 27, -14, | ||
| 788 | }, { | ||
| 789 | 32, -44, 39, -31, 21, -10, -2, 14, -25, 34, -41, 45, -45, 42, -36, 28, | ||
| 790 | -17, 6, 7, -18, 29, -37, 43, -45, 44, -40, 34, -24, 13, -1, -11, 22, | ||
| 791 | -32, 39, -44, 45, -43, 38, -30, 20, -9, -3, 15, -26, 35, -41, 45, -45, | ||
| 792 | 42, -36, 27, -16, 4, 8, -19, 30, -38, 43, -45, 44, -40, 33, -23, 12, | ||
| 793 | }, { | ||
| 794 | 32, -44, 41, -36, 29, -20, 11, -1, -9, 18, -27, 34, -40, 44, -45, 45, | ||
| 795 | -42, 37, -30, 22, -13, 3, 7, -16, 25, -33, 39, -43, 45, -45, 43, -38, | ||
| 796 | 32, -24, 15, -6, -4, 14, -23, 31, -38, 42, -45, 45, -43, 39, -34, 26, | ||
| 797 | -17, 8, 2, -12, 21, -30, 36, -41, 44, -45, 44, -40, 35, -28, 19, -10, | ||
| 798 | }, { | ||
| 799 | 32, -45, 43, -39, 35, -30, 23, -16, 9, -1, -7, 14, -21, 28, -34, 38, | ||
| 800 | -42, 44, -45, 45, -43, 40, -36, 31, -25, 18, -11, 3, 4, -12, 19, -26, | ||
| 801 | 32, -37, 41, -44, 45, -45, 44, -41, 38, -33, 27, -20, 13, -6, -2, 10, | ||
| 802 | -17, 24, -30, 36, -40, 43, -45, 45, -44, 42, -39, 34, -29, 22, -15, 8, | ||
| 803 | }, { | ||
| 804 | 32, -45, 44, -42, 40, -37, 34, -30, 25, -20, 15, -10, 4, 1, -7, 12, | ||
| 805 | -17, 22, -27, 31, -35, 38, -41, 43, -44, 45, -45, 45, -43, 41, -39, 36, | ||
| 806 | -32, 28, -23, 18, -13, 8, -2, -3, 9, -14, 19, -24, 29, -33, 36, -39, | ||
| 807 | 42, -44, 45, -45, 45, -44, 43, -40, 38, -34, 30, -26, 21, -16, 11, -6, | ||
| 808 | }, { | ||
| 809 | 32, -45, 45, -44, 43, -42, 41, -39, 38, -36, 34, -31, 29, -26, 23, -20, | ||
| 810 | 17, -14, 11, -8, 4, -1, -2, 6, -9, 12, -15, 18, -21, 24, -27, 30, | ||
| 811 | -32, 34, -36, 38, -40, 41, -43, 44, -44, 45, -45, 45, -45, 45, -44, 43, | ||
| 812 | -42, 40, -39, 37, -35, 33, -30, 28, -25, 22, -19, 16, -13, 10, -7, 3, | ||
| 813 | }, { | ||
| 814 | 32, -45, 45, -45, 45, -45, 45, -45, 44, -44, 44, -44, 43, -43, 43, -42, | ||
| 815 | 42, -41, 41, -40, 40, -39, 39, -38, 38, -37, 36, -36, 35, -34, 34, -33, | ||
| 816 | 32, -31, 30, -30, 29, -28, 27, -26, 25, -24, 23, -22, 21, -20, 19, -18, | ||
| 817 | 17, -16, 15, -14, 13, -12, 11, -10, 9, -8, 7, -6, 4, -3, 2, -1, | ||
| 818 | } | ||
| 819 | }; | ||
| 820 | |||
| 821 | struct H274HashContext { | ||
| 822 | int type; | ||
| 823 | struct AVMD5 *ctx; | ||
| 824 | |||
| 825 | #if HAVE_BIGENDIAN | ||
| 826 | BswapDSPContext bdsp; | ||
| 827 | uint8_t *buf; | ||
| 828 | int buf_size; | ||
| 829 | #endif | ||
| 830 | }; | ||
| 831 | |||
| 832 | ✗ | static av_always_inline void bswap16_buf_if_be(H274HashContext *s, const int ps, const uint8_t **src, const int w) | |
| 833 | { | ||
| 834 | #if HAVE_BIGENDIAN | ||
| 835 | if (ps) { | ||
| 836 | s->bdsp.bswap16_buf((uint16_t *)s->buf, | ||
| 837 | (const uint16_t *)*src, w); | ||
| 838 | *src = s->buf; | ||
| 839 | } | ||
| 840 | #endif | ||
| 841 | ✗ | } | |
| 842 | |||
| 843 | ✗ | static int verify_plane_md5(H274HashContext *s, | |
| 844 | const uint8_t *_src, const int w, const int h, const int stride, | ||
| 845 | const int ps, const uint8_t *expected) | ||
| 846 | { | ||
| 847 | #define MD5_SIZE 16 | ||
| 848 | ✗ | struct AVMD5 *ctx = s->ctx; | |
| 849 | uint8_t md5[MD5_SIZE]; | ||
| 850 | |||
| 851 | ✗ | av_md5_init(ctx); | |
| 852 | ✗ | for (int j = 0; j < h; j++) { | |
| 853 | ✗ | const uint8_t *src = &_src[j * stride]; | |
| 854 | ✗ | bswap16_buf_if_be(s, ps, &src, w); | |
| 855 | ✗ | av_md5_update(ctx, src, w << ps); | |
| 856 | ✗ | src += stride; | |
| 857 | } | ||
| 858 | ✗ | av_md5_final(ctx, md5); | |
| 859 | |||
| 860 | ✗ | if (memcmp(md5, expected, MD5_SIZE)) | |
| 861 | ✗ | return AVERROR_INVALIDDATA; | |
| 862 | |||
| 863 | ✗ | return 0; | |
| 864 | } | ||
| 865 | |||
| 866 | ✗ | static int verify_plane_crc(H274HashContext *s, const uint8_t *_src, const int w, const int h, const int stride, | |
| 867 | const int ps, uint16_t expected) | ||
| 868 | { | ||
| 869 | ✗ | uint32_t crc = 0x0F1D; // CRC-16-CCITT-AUG | |
| 870 | ✗ | const AVCRC *ctx = av_crc_get_table(AV_CRC_16_CCITT); | |
| 871 | |||
| 872 | ✗ | for (int j = 0; j < h; j++) { | |
| 873 | ✗ | const uint8_t *src = &_src[j * stride]; | |
| 874 | ✗ | bswap16_buf_if_be(s, ps, &src, w); | |
| 875 | ✗ | crc = av_crc(ctx, crc, src, w << ps); | |
| 876 | ✗ | src += stride; | |
| 877 | } | ||
| 878 | ✗ | crc = av_bswap16(crc); | |
| 879 | |||
| 880 | ✗ | if (crc != expected) | |
| 881 | ✗ | return AVERROR_INVALIDDATA; | |
| 882 | |||
| 883 | ✗ | return 0; | |
| 884 | } | ||
| 885 | |||
| 886 | #define CAL_CHECKSUM(pixel) ((pixel) ^ xor_mask) | ||
| 887 | ✗ | static int verify_plane_checksum(const uint8_t *src, const int w, const int h, const int stride, const int ps, | |
| 888 | uint32_t expected) | ||
| 889 | { | ||
| 890 | ✗ | uint32_t checksum = 0; | |
| 891 | ✗ | expected = av_le2ne32(expected); | |
| 892 | |||
| 893 | ✗ | for (int y = 0; y < h; y++) { | |
| 894 | ✗ | for (int x = 0; x < w; x++) { | |
| 895 | ✗ | const int xor_mask = (x & 0xFF) ^ (y & 0xFF) ^ (x >> 8) ^ (y >> 8); | |
| 896 | ✗ | checksum += CAL_CHECKSUM(src[x << ps]); | |
| 897 | ✗ | if (ps) | |
| 898 | ✗ | checksum += CAL_CHECKSUM(src[(x << ps) + 1]); | |
| 899 | } | ||
| 900 | ✗ | src += stride; | |
| 901 | } | ||
| 902 | |||
| 903 | ✗ | if (checksum != expected) | |
| 904 | ✗ | return AVERROR_INVALIDDATA; | |
| 905 | |||
| 906 | ✗ | return 0; | |
| 907 | } | ||
| 908 | |||
| 909 | enum { | ||
| 910 | HASH_MD5SUM, | ||
| 911 | HASH_CRC, | ||
| 912 | HASH_CHECKSUM, | ||
| 913 | HASH_LAST = HASH_CHECKSUM, | ||
| 914 | }; | ||
| 915 | |||
| 916 | 94 | void ff_h274_hash_freep(H274HashContext **ctx) | |
| 917 | { | ||
| 918 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 94 times.
|
94 | if (*ctx) { |
| 919 | ✗ | H274HashContext *c = *ctx; | |
| 920 | ✗ | if (c->ctx) | |
| 921 | ✗ | av_free(c->ctx); | |
| 922 | ✗ | av_freep(ctx); | |
| 923 | #if HAVE_BIGENDIAN | ||
| 924 | av_freep(&c->buf); | ||
| 925 | #endif | ||
| 926 | } | ||
| 927 | 94 | } | |
| 928 | |||
| 929 | ✗ | int ff_h274_hash_init(H274HashContext **ctx, const int type) | |
| 930 | { | ||
| 931 | H274HashContext *c; | ||
| 932 | |||
| 933 | ✗ | if (type > HASH_LAST || !ctx) | |
| 934 | ✗ | return AVERROR(EINVAL); | |
| 935 | |||
| 936 | ✗ | c = *ctx; | |
| 937 | ✗ | if (c) { | |
| 938 | ✗ | if (c->type != type) { | |
| 939 | ✗ | if (c->type == HASH_MD5SUM) | |
| 940 | ✗ | av_freep(&c->ctx); | |
| 941 | ✗ | c->type = type; | |
| 942 | } | ||
| 943 | } else { | ||
| 944 | ✗ | c = av_mallocz(sizeof(H274HashContext)); | |
| 945 | ✗ | if (!c) | |
| 946 | ✗ | return AVERROR(ENOMEM); | |
| 947 | ✗ | c->type = type; | |
| 948 | ✗ | *ctx = c; | |
| 949 | } | ||
| 950 | |||
| 951 | ✗ | if (type == HASH_MD5SUM && !c->ctx) { | |
| 952 | ✗ | c->ctx = av_md5_alloc(); | |
| 953 | ✗ | if (!c->ctx) | |
| 954 | ✗ | return AVERROR(ENOMEM); | |
| 955 | } | ||
| 956 | |||
| 957 | #if HAVE_BIGENDIAN | ||
| 958 | ff_bswapdsp_init(&c->bdsp); | ||
| 959 | #endif | ||
| 960 | |||
| 961 | ✗ | return 0; | |
| 962 | } | ||
| 963 | |||
| 964 | ✗ | int ff_h274_hash_verify(H274HashContext *c, const H274SEIPictureHash *hash, | |
| 965 | const AVFrame *frame, const int coded_width, const int coded_height) | ||
| 966 | { | ||
| 967 | const AVPixFmtDescriptor *desc; | ||
| 968 | ✗ | int err = 0; | |
| 969 | |||
| 970 | ✗ | if (!c || !hash || !frame) | |
| 971 | ✗ | return AVERROR(EINVAL); | |
| 972 | |||
| 973 | ✗ | if (c->type != hash->hash_type) | |
| 974 | ✗ | return AVERROR(EINVAL); | |
| 975 | |||
| 976 | ✗ | desc = av_pix_fmt_desc_get(frame->format); | |
| 977 | ✗ | if (!desc) | |
| 978 | ✗ | return AVERROR(EINVAL); | |
| 979 | |||
| 980 | ✗ | for (int i = 0; i < desc->nb_components; i++) { | |
| 981 | ✗ | const int w = i ? (coded_width >> desc->log2_chroma_w) : coded_width; | |
| 982 | ✗ | const int h = i ? (coded_height >> desc->log2_chroma_h) : coded_height; | |
| 983 | ✗ | const int ps = desc->comp[i].step - 1; | |
| 984 | ✗ | const uint8_t *src = frame->data[i]; | |
| 985 | ✗ | const int stride = frame->linesize[i]; | |
| 986 | |||
| 987 | #if HAVE_BIGENDIAN | ||
| 988 | if (c->type != HASH_CHECKSUM) { | ||
| 989 | if (ps) { | ||
| 990 | av_fast_malloc(&c->buf, &c->buf_size, | ||
| 991 | FFMAX3(frame->linesize[0], frame->linesize[1], | ||
| 992 | frame->linesize[2])); | ||
| 993 | if (!c->buf) | ||
| 994 | return AVERROR(ENOMEM); | ||
| 995 | } | ||
| 996 | } | ||
| 997 | #endif | ||
| 998 | |||
| 999 | ✗ | if (c->type == HASH_MD5SUM) | |
| 1000 | ✗ | err = verify_plane_md5(c, src, w, h, stride, ps, hash->md5[i]); | |
| 1001 | ✗ | else if (c->type == HASH_CRC) | |
| 1002 | ✗ | err = verify_plane_crc(c, src, w, h, stride, ps, hash->crc[i]); | |
| 1003 | ✗ | else if (c->type == HASH_CHECKSUM) | |
| 1004 | ✗ | err = verify_plane_checksum(src, w, h, stride, ps, hash->checksum[i]); | |
| 1005 | ✗ | if (err < 0) | |
| 1006 | ✗ | goto fail; | |
| 1007 | } | ||
| 1008 | |||
| 1009 | ✗ | fail: | |
| 1010 | ✗ | return err; | |
| 1011 | } | ||
| 1012 |