FFmpeg coverage

Directory: ../../../ffmpeg/
File: src/libavcodec/aom_film_grain.c
Date: 2024-11-20 23:03:26
Exec Total Coverage
Lines: 8 221 3.6%
Functions: 2 6 33.3%
Branches: 3 139 2.2%
Line Branch Exec Source
1 /*
2 * AOM film grain synthesis
3 * Copyright (c) 2023 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 * AOM film grain synthesis.
25 * @author Niklas Haas <ffmpeg@haasn.xyz>
26 */
27
28 #include "libavutil/avassert.h"
29 #include "libavutil/buffer.h"
30 #include "libavutil/imgutils.h"
31 #include "libavutil/mem.h"
32
33 #include "aom_film_grain.h"
34 #include "get_bits.h"
35
36 // Common/shared helpers (not dependent on BIT_DEPTH)
37 ✗ static inline int get_random_number(const int bits, unsigned *const state) {
38 ✗ const int r = *state;
39 ✗ unsigned bit = ((r >> 0) ^ (r >> 1) ^ (r >> 3) ^ (r >> 12)) & 1;
40 ✗ *state = (r >> 1) | (bit << 15);
41
42 ✗ return (*state >> (16 - bits)) & ((1 << bits) - 1);
43 }
44
45 ✗ static inline int round2(const int x, const uint64_t shift) {
46 ✗ return (x + ((1 << shift) >> 1)) >> shift;
47 }
48
49 enum {
50 GRAIN_WIDTH = 82,
51 GRAIN_HEIGHT = 73,
52 SUB_GRAIN_WIDTH = 44,
53 SUB_GRAIN_HEIGHT = 38,
54 FG_BLOCK_SIZE = 32,
55 };
56
57 static const int16_t gaussian_sequence[2048];
58
59 #define BIT_DEPTH 16
60 #include "aom_film_grain_template.c"
61 #undef BIT_DEPTH
62
63 #define BIT_DEPTH 8
64 #include "aom_film_grain_template.c"
65 #undef BIT_DEPTH
66
67
68 ✗ int ff_aom_apply_film_grain(AVFrame *out, const AVFrame *in,
69 const AVFilmGrainParams *params)
70 {
71 ✗ const AVFilmGrainAOMParams *const data = &params->codec.aom;
72 ✗ const AVPixFmtDescriptor *desc = av_pix_fmt_desc_get(out->format);
73 ✗ const int subx = desc->log2_chroma_w, suby = desc->log2_chroma_h;
74 ✗ const int pxstep = desc->comp[0].step;
75
76 ✗ av_assert0(out->format == in->format);
77 ✗ av_assert0(params->type == AV_FILM_GRAIN_PARAMS_AV1);
78
79 // Copy over the non-modified planes
80 ✗ if (!params->codec.aom.num_y_points) {
81 ✗ av_image_copy_plane(out->data[0], out->linesize[0],
82 ✗ in->data[0], in->linesize[0],
83 ✗ out->width * pxstep, out->height);
84 }
85 ✗ for (int uv = 0; uv < 2; uv++) {
86 ✗ if (!data->num_uv_points[uv]) {
87 ✗ av_image_copy_plane(out->data[1+uv], out->linesize[1+uv],
88 ✗ in->data[1+uv], in->linesize[1+uv],
89 ✗ AV_CEIL_RSHIFT(out->width, subx) * pxstep,
90 ✗ AV_CEIL_RSHIFT(out->height, suby));
91 }
92 }
93
94 ✗ switch (in->format) {
95 ✗ case AV_PIX_FMT_GRAY8:
96 case AV_PIX_FMT_YUV420P:
97 case AV_PIX_FMT_YUV422P:
98 case AV_PIX_FMT_YUV444P:
99 case AV_PIX_FMT_YUVJ420P:
100 case AV_PIX_FMT_YUVJ422P:
101 case AV_PIX_FMT_YUVJ444P:
102 ✗ return apply_film_grain_8(out, in, params);
103 ✗ case AV_PIX_FMT_GRAY9:
104 case AV_PIX_FMT_YUV420P9:
105 case AV_PIX_FMT_YUV422P9:
106 case AV_PIX_FMT_YUV444P9:
107 ✗ return apply_film_grain_16(out, in, params, 9);
108 ✗ case AV_PIX_FMT_GRAY10:
109 case AV_PIX_FMT_YUV420P10:
110 case AV_PIX_FMT_YUV422P10:
111 case AV_PIX_FMT_YUV444P10:
112 ✗ return apply_film_grain_16(out, in, params, 10);
113 ✗ case AV_PIX_FMT_GRAY12:
114 case AV_PIX_FMT_YUV420P12:
115 case AV_PIX_FMT_YUV422P12:
116 case AV_PIX_FMT_YUV444P12:
117 ✗ return apply_film_grain_16(out, in, params, 12);
118 }
119
120 /* The AV1 spec only defines film grain synthesis for these formats */
121 ✗ return AVERROR_INVALIDDATA;
122 }
123
124 ✗ int ff_aom_parse_film_grain_sets(AVFilmGrainAFGS1Params *s,
125 const uint8_t *payload, int payload_size)
126 {
127 ✗ GetBitContext gbc, *gb = &gbc;
128 AVFilmGrainAOMParams *aom;
129 ✗ AVFilmGrainParams *fgp = NULL, *ref = NULL;
130 int ret, num_sets, n, i, uv, num_y_coeffs, update_grain, luma_only;
131
132 ✗ ret = init_get_bits8(gb, payload, payload_size);
133 ✗ if (ret < 0)
134 ✗ return ret;
135
136 ✗ s->enable = get_bits1(gb);
137 ✗ if (!s->enable)
138 ✗ return 0;
139
140 ✗ for (int i = 0; i < FF_ARRAY_ELEMS(s->sets); i++)
141 ✗ av_buffer_unref(&s->sets[i]);
142
143 ✗ skip_bits(gb, 4); // reserved
144 ✗ num_sets = get_bits(gb, 3) + 1;
145 ✗ for (n = 0; n < num_sets; n++) {
146 int payload_4byte, payload_size, set_idx, apply_units_log2, vsc_flag;
147 int predict_scaling, predict_y_scaling, predict_uv_scaling[2];
148 int payload_bits, start_position;
149 size_t fgp_size;
150
151 ✗ start_position = get_bits_count(gb);
152 ✗ payload_4byte = get_bits1(gb);
153 ✗ payload_size = get_bits(gb, payload_4byte ? 2 : 8);
154 ✗ set_idx = get_bits(gb, 3);
155 ✗ fgp = av_film_grain_params_alloc(&fgp_size);
156 ✗ if (!fgp)
157 ✗ goto error;
158 ✗ aom = &fgp->codec.aom;
159
160 ✗ fgp->type = get_bits1(gb) ? AV_FILM_GRAIN_PARAMS_AV1 : AV_FILM_GRAIN_PARAMS_NONE;
161 ✗ if (!fgp->type) {
162 ✗ av_freep(&fgp);
163 ✗ continue;
164 }
165
166 ✗ fgp->seed = get_bits(gb, 16);
167 ✗ update_grain = get_bits1(gb);
168 ✗ if (!update_grain) {
169 ✗ av_freep(&fgp);
170 ✗ continue;
171 }
172
173 ✗ apply_units_log2 = get_bits(gb, 4);
174 ✗ fgp->width = get_bits(gb, 12) << apply_units_log2;
175 ✗ fgp->height = get_bits(gb, 12) << apply_units_log2;
176 ✗ luma_only = get_bits1(gb);
177 ✗ if (luma_only) {
178 ✗ fgp->subsampling_x = fgp->subsampling_y = 0;
179 } else {
180 ✗ fgp->subsampling_x = get_bits1(gb);
181 ✗ fgp->subsampling_y = get_bits1(gb);
182 }
183
184 ✗ fgp->bit_depth_luma = fgp->bit_depth_chroma = 0;
185 ✗ fgp->color_primaries = AVCOL_PRI_UNSPECIFIED;
186 ✗ fgp->color_trc = AVCOL_TRC_UNSPECIFIED;
187 ✗ fgp->color_space = AVCOL_SPC_UNSPECIFIED;
188 ✗ fgp->color_range = AVCOL_RANGE_UNSPECIFIED;
189
190 ✗ vsc_flag = get_bits1(gb); // video_signal_characteristics_flag
191 ✗ if (vsc_flag) {
192 int cicp_flag;
193 ✗ fgp->bit_depth_luma = get_bits(gb, 3) + 8;
194 ✗ if (!luma_only)
195 ✗ fgp->bit_depth_chroma = fgp->bit_depth_luma;
196 ✗ cicp_flag = get_bits1(gb);
197 ✗ if (cicp_flag) {
198 ✗ fgp->color_primaries = get_bits(gb, 8);
199 ✗ fgp->color_trc = get_bits(gb, 8);
200 ✗ fgp->color_space = get_bits(gb, 8);
201 ✗ fgp->color_range = get_bits1(gb) ? AVCOL_RANGE_JPEG : AVCOL_RANGE_MPEG;
202 ✗ if (fgp->color_primaries > AVCOL_PRI_NB ||
203 ✗ fgp->color_primaries == AVCOL_PRI_RESERVED ||
204 ✗ fgp->color_primaries == AVCOL_PRI_RESERVED0 ||
205 ✗ fgp->color_trc > AVCOL_TRC_NB ||
206 ✗ fgp->color_trc == AVCOL_TRC_RESERVED ||
207 ✗ fgp->color_trc == AVCOL_TRC_RESERVED0 ||
208 ✗ fgp->color_space > AVCOL_SPC_NB ||
209 ✗ fgp->color_space == AVCOL_SPC_RESERVED)
210 ✗ goto error;
211 }
212 }
213
214 ✗ predict_scaling = get_bits1(gb);
215 ✗ if (predict_scaling && (!ref || ref == fgp))
216 ✗ goto error; // prediction must be from valid, different set
217
218 ✗ predict_y_scaling = predict_scaling ? get_bits1(gb) : 0;
219 ✗ if (predict_y_scaling) {
220 int y_scale, y_offset, bits_res;
221 ✗ y_scale = get_bits(gb, 9) - 256;
222 ✗ y_offset = get_bits(gb, 9) - 256;
223 ✗ bits_res = get_bits(gb, 3);
224 ✗ if (bits_res) {
225 int res[14], pred, granularity;
226 ✗ aom->num_y_points = ref->codec.aom.num_y_points;
227 ✗ for (i = 0; i < aom->num_y_points; i++)
228 ✗ res[i] = get_bits(gb, bits_res);
229 ✗ granularity = get_bits(gb, 3);
230 ✗ for (i = 0; i < aom->num_y_points; i++) {
231 ✗ pred = ref->codec.aom.y_points[i][1];
232 ✗ pred = ((pred * y_scale + 8) >> 4) + y_offset;
233 ✗ pred += (res[i] - (1 << (bits_res - 1))) * granularity;
234 ✗ aom->y_points[i][0] = ref->codec.aom.y_points[i][0];
235 ✗ aom->y_points[i][1] = av_clip_uint8(pred);
236 }
237 }
238 } else {
239 ✗ aom->num_y_points = get_bits(gb, 4);
240 ✗ if (aom->num_y_points > 14) {
241 ✗ goto error;
242 ✗ } else if (aom->num_y_points) {
243 int bits_inc, bits_scaling;
244 ✗ int y_value = 0;
245 ✗ bits_inc = get_bits(gb, 3) + 1;
246 ✗ bits_scaling = get_bits(gb, 2) + 5;
247 ✗ for (i = 0; i < aom->num_y_points; i++) {
248 ✗ y_value += get_bits(gb, bits_inc);
249 ✗ if (y_value > UINT8_MAX)
250 ✗ goto error;
251 ✗ aom->y_points[i][0] = y_value;
252 ✗ aom->y_points[i][1] = get_bits(gb, bits_scaling);
253 }
254 }
255 }
256
257 ✗ if (luma_only) {
258 ✗ aom->chroma_scaling_from_luma = 0;
259 ✗ aom->num_uv_points[0] = aom->num_uv_points[1] = 0;
260 } else {
261 ✗ aom->chroma_scaling_from_luma = get_bits1(gb);
262 ✗ if (aom->chroma_scaling_from_luma) {
263 ✗ aom->num_uv_points[0] = aom->num_uv_points[1] = 0;
264 } else {
265 ✗ for (uv = 0; uv < 2; uv++) {
266 ✗ predict_uv_scaling[uv] = predict_scaling ? get_bits1(gb) : 0;
267 ✗ if (predict_uv_scaling[uv]) {
268 int uv_scale, uv_offset, bits_res;
269 ✗ uv_scale = get_bits(gb, 9) - 256;
270 ✗ uv_offset = get_bits(gb, 9) - 256;
271 ✗ bits_res = get_bits(gb, 3);
272 ✗ aom->uv_mult[uv] = ref->codec.aom.uv_mult[uv];
273 ✗ aom->uv_mult_luma[uv] = ref->codec.aom.uv_mult_luma[uv];
274 ✗ aom->uv_offset[uv] = ref->codec.aom.uv_offset[uv];
275 ✗ if (bits_res) {
276 int res[10], pred, granularity;
277 ✗ aom->num_uv_points[uv] = ref->codec.aom.num_uv_points[uv];
278 ✗ for (i = 0; i < aom->num_uv_points[uv]; i++)
279 ✗ res[i] = get_bits(gb, bits_res);
280 ✗ granularity = get_bits(gb, 3);
281 ✗ for (i = 0; i < aom->num_uv_points[uv]; i++) {
282 ✗ pred = ref->codec.aom.uv_points[uv][i][1];
283 ✗ pred = ((pred * uv_scale + 8) >> 4) + uv_offset;
284 ✗ pred += (res[i] - (1 << (bits_res - 1))) * granularity;
285 ✗ aom->uv_points[uv][i][0] = ref->codec.aom.uv_points[uv][i][0];
286 ✗ aom->uv_points[uv][i][1] = av_clip_uint8(pred);
287 }
288 }
289 } else {
290 int bits_inc, bits_scaling, uv_offset;
291 ✗ int uv_value = 0;
292 ✗ aom->num_uv_points[uv] = get_bits(gb, 4);
293 ✗ if (aom->num_uv_points[uv] > 10)
294 ✗ goto error;
295 ✗ bits_inc = get_bits(gb, 3) + 1;
296 ✗ bits_scaling = get_bits(gb, 2) + 5;
297 ✗ uv_offset = get_bits(gb, 8);
298 ✗ for (i = 0; i < aom->num_uv_points[uv]; i++) {
299 ✗ uv_value += get_bits(gb, bits_inc);
300 ✗ if (uv_value > UINT8_MAX)
301 ✗ goto error;
302 ✗ aom->uv_points[uv][i][0] = uv_value;
303 ✗ aom->uv_points[uv][i][1] = get_bits(gb, bits_scaling) + uv_offset;
304 }
305 }
306 }
307 }
308 }
309
310 ✗ aom->scaling_shift = get_bits(gb, 2) + 8;
311 ✗ aom->ar_coeff_lag = get_bits(gb, 2);
312 ✗ num_y_coeffs = 2 * aom->ar_coeff_lag * (aom->ar_coeff_lag + 1);
313 ✗ if (aom->num_y_points) {
314 ✗ int ar_bits = get_bits(gb, 2) + 5;
315 ✗ for (i = 0; i < num_y_coeffs; i++)
316 ✗ aom->ar_coeffs_y[i] = get_bits(gb, ar_bits) - (1 << (ar_bits - 1));
317 }
318 ✗ for (uv = 0; uv < 2; uv++) {
319 ✗ if (aom->chroma_scaling_from_luma || aom->num_uv_points[uv]) {
320 ✗ int ar_bits = get_bits(gb, 2) + 5;
321 ✗ for (i = 0; i < num_y_coeffs + !!aom->num_y_points; i++)
322 ✗ aom->ar_coeffs_uv[uv][i] = get_bits(gb, ar_bits) - (1 << (ar_bits - 1));
323 }
324 }
325 ✗ aom->ar_coeff_shift = get_bits(gb, 2) + 6;
326 ✗ aom->grain_scale_shift = get_bits(gb, 2);
327 ✗ for (uv = 0; uv < 2; uv++) {
328 ✗ if (aom->num_uv_points[uv] && !predict_uv_scaling[uv]) {
329 ✗ aom->uv_mult[uv] = get_bits(gb, 8) - 128;
330 ✗ aom->uv_mult_luma[uv] = get_bits(gb, 8) - 128;
331 ✗ aom->uv_offset[uv] = get_bits(gb, 9) - 256;
332 }
333 }
334 ✗ aom->overlap_flag = get_bits1(gb);
335 ✗ aom->limit_output_range = get_bits1(gb);
336
337 // use first set as reference only if it was fully transmitted
338 ✗ if (n == 0)
339 ✗ ref = fgp;
340
341 ✗ payload_bits = get_bits_count(gb) - start_position;
342 ✗ if (payload_bits > payload_size * 8)
343 ✗ goto error;
344 ✗ skip_bits(gb, payload_size * 8 - payload_bits);
345
346 ✗ av_buffer_unref(&s->sets[set_idx]);
347 ✗ s->sets[set_idx] = av_buffer_create((uint8_t *)fgp, fgp_size, NULL, NULL, 0);
348 ✗ if (!s->sets[set_idx])
349 ✗ goto error;
350 }
351 ✗ return 0;
352
353 ✗ error:
354 ✗ av_free(fgp);
355 ✗ ff_aom_uninit_film_grain_params(s);
356 ✗ return AVERROR_INVALIDDATA;
357 }
358
359 35102 int ff_aom_attach_film_grain_sets(const AVFilmGrainAFGS1Params *s, AVFrame *frame)
360 {
361
1/2
✓ Branch 0 taken 35102 times.
✗ Branch 1 not taken.
 35102 if (!s->enable)
362 35102 return 0;
363
364 ✗ for (int i = 0; i < FF_ARRAY_ELEMS(s->sets); i++) {
365 AVBufferRef *buf;
366
367 ✗ if (!s->sets[i])
368 ✗ continue;
369
370 ✗ buf = av_buffer_ref(s->sets[i]);
371 ✗ if (!buf || !av_frame_new_side_data_from_buf(frame,
372 AV_FRAME_DATA_FILM_GRAIN_PARAMS, buf)) {
373 ✗ av_buffer_unref(&buf);
374 ✗ return AVERROR(ENOMEM);
375 }
376 }
377
378 ✗ return 0;
379 }
380
381 73911 void ff_aom_uninit_film_grain_params(AVFilmGrainAFGS1Params *s)
382 {
383
2/2
✓ Branch 0 taken 591288 times.
✓ Branch 1 taken 73911 times.
 665199 for (int i = 0; i < FF_ARRAY_ELEMS(s->sets); i++)
384 591288 av_buffer_unref(&s->sets[i]);
385 73911 s->enable = 0;
386 73911 }
387
388 // Taken from the AV1 spec. Range is [-2048, 2047], mean is 0 and stddev is 512
389 static const int16_t gaussian_sequence[2048] = {
390 56, 568, -180, 172, 124, -84, 172, -64, -900, 24, 820,
391 224, 1248, 996, 272, -8, -916, -388, -732, -104, -188, 800,
392 112, -652, -320, -376, 140, -252, 492, -168, 44, -788, 588,
393 -584, 500, -228, 12, 680, 272, -476, 972, -100, 652, 368,
394 432, -196, -720, -192, 1000, -332, 652, -136, -552, -604, -4,
395 192, -220, -136, 1000, -52, 372, -96, -624, 124, -24, 396,
396 540, -12, -104, 640, 464, 244, -208, -84, 368, -528, -740,
397 248, -968, -848, 608, 376, -60, -292, -40, -156, 252, -292,
398 248, 224, -280, 400, -244, 244, -60, 76, -80, 212, 532,
399 340, 128, -36, 824, -352, -60, -264, -96, -612, 416, -704,
400 220, -204, 640, -160, 1220, -408, 900, 336, 20, -336, -96,
401 -792, 304, 48, -28, -1232, -1172, -448, 104, -292, -520, 244,
402 60, -948, 0, -708, 268, 108, 356, -548, 488, -344, -136,
403 488, -196, -224, 656, -236, -1128, 60, 4, 140, 276, -676,
404 -376, 168, -108, 464, 8, 564, 64, 240, 308, -300, -400,
405 -456, -136, 56, 120, -408, -116, 436, 504, -232, 328, 844,
406 -164, -84, 784, -168, 232, -224, 348, -376, 128, 568, 96,
407 -1244, -288, 276, 848, 832, -360, 656, 464, -384, -332, -356,
408 728, -388, 160, -192, 468, 296, 224, 140, -776, -100, 280,
409 4, 196, 44, -36, -648, 932, 16, 1428, 28, 528, 808,
410 772, 20, 268, 88, -332, -284, 124, -384, -448, 208, -228,
411 -1044, -328, 660, 380, -148, -300, 588, 240, 540, 28, 136,
412 -88, -436, 256, 296, -1000, 1400, 0, -48, 1056, -136, 264,
413 -528, -1108, 632, -484, -592, -344, 796, 124, -668, -768, 388,
414 1296, -232, -188, -200, -288, -4, 308, 100, -168, 256, -500,
415 204, -508, 648, -136, 372, -272, -120, -1004, -552, -548, -384,
416 548, -296, 428, -108, -8, -912, -324, -224, -88, -112, -220,
417 -100, 996, -796, 548, 360, -216, 180, 428, -200, -212, 148,
418 96, 148, 284, 216, -412, -320, 120, -300, -384, -604, -572,
419 -332, -8, -180, -176, 696, 116, -88, 628, 76, 44, -516,
420 240, -208, -40, 100, -592, 344, -308, -452, -228, 20, 916,
421 -1752, -136, -340, -804, 140, 40, 512, 340, 248, 184, -492,
422 896, -156, 932, -628, 328, -688, -448, -616, -752, -100, 560,
423 -1020, 180, -800, -64, 76, 576, 1068, 396, 660, 552, -108,
424 -28, 320, -628, 312, -92, -92, -472, 268, 16, 560, 516,
425 -672, -52, 492, -100, 260, 384, 284, 292, 304, -148, 88,
426 -152, 1012, 1064, -228, 164, -376, -684, 592, -392, 156, 196,
427 -524, -64, -884, 160, -176, 636, 648, 404, -396, -436, 864,
428 424, -728, 988, -604, 904, -592, 296, -224, 536, -176, -920,
429 436, -48, 1176, -884, 416, -776, -824, -884, 524, -548, -564,
430 -68, -164, -96, 692, 364, -692, -1012, -68, 260, -480, 876,
431 -1116, 452, -332, -352, 892, -1088, 1220, -676, 12, -292, 244,
432 496, 372, -32, 280, 200, 112, -440, -96, 24, -644, -184,
433 56, -432, 224, -980, 272, -260, 144, -436, 420, 356, 364,
434 -528, 76, 172, -744, -368, 404, -752, -416, 684, -688, 72,
435 540, 416, 92, 444, 480, -72, -1416, 164, -1172, -68, 24,
436 424, 264, 1040, 128, -912, -524, -356, 64, 876, -12, 4,
437 -88, 532, 272, -524, 320, 276, -508, 940, 24, -400, -120,
438 756, 60, 236, -412, 100, 376, -484, 400, -100, -740, -108,
439 -260, 328, -268, 224, -200, -416, 184, -604, -564, -20, 296,
440 60, 892, -888, 60, 164, 68, -760, 216, -296, 904, -336,
441 -28, 404, -356, -568, -208, -1480, -512, 296, 328, -360, -164,
442 -1560, -776, 1156, -428, 164, -504, -112, 120, -216, -148, -264,
443 308, 32, 64, -72, 72, 116, 176, -64, -272, 460, -536,
444 -784, -280, 348, 108, -752, -132, 524, -540, -776, 116, -296,
445 -1196, -288, -560, 1040, -472, 116, -848, -1116, 116, 636, 696,
446 284, -176, 1016, 204, -864, -648, -248, 356, 972, -584, -204,
447 264, 880, 528, -24, -184, 116, 448, -144, 828, 524, 212,
448 -212, 52, 12, 200, 268, -488, -404, -880, 824, -672, -40,
449 908, -248, 500, 716, -576, 492, -576, 16, 720, -108, 384,
450 124, 344, 280, 576, -500, 252, 104, -308, 196, -188, -8,
451 1268, 296, 1032, -1196, 436, 316, 372, -432, -200, -660, 704,
452 -224, 596, -132, 268, 32, -452, 884, 104, -1008, 424, -1348,
453 -280, 4, -1168, 368, 476, 696, 300, -8, 24, 180, -592,
454 -196, 388, 304, 500, 724, -160, 244, -84, 272, -256, -420,
455 320, 208, -144, -156, 156, 364, 452, 28, 540, 316, 220,
456 -644, -248, 464, 72, 360, 32, -388, 496, -680, -48, 208,
457 -116, -408, 60, -604, -392, 548, -840, 784, -460, 656, -544,
458 -388, -264, 908, -800, -628, -612, -568, 572, -220, 164, 288,
459 -16, -308, 308, -112, -636, -760, 280, -668, 432, 364, 240,
460 -196, 604, 340, 384, 196, 592, -44, -500, 432, -580, -132,
461 636, -76, 392, 4, -412, 540, 508, 328, -356, -36, 16,
462 -220, -64, -248, -60, 24, -192, 368, 1040, 92, -24, -1044,
463 -32, 40, 104, 148, 192, -136, -520, 56, -816, -224, 732,
464 392, 356, 212, -80, -424, -1008, -324, 588, -1496, 576, 460,
465 -816, -848, 56, -580, -92, -1372, -112, -496, 200, 364, 52,
466 -140, 48, -48, -60, 84, 72, 40, 132, -356, -268, -104,
467 -284, -404, 732, -520, 164, -304, -540, 120, 328, -76, -460,
468 756, 388, 588, 236, -436, -72, -176, -404, -316, -148, 716,
469 -604, 404, -72, -88, -888, -68, 944, 88, -220, -344, 960,
470 472, 460, -232, 704, 120, 832, -228, 692, -508, 132, -476,
471 844, -748, -364, -44, 1116, -1104, -1056, 76, 428, 552, -692,
472 60, 356, 96, -384, -188, -612, -576, 736, 508, 892, 352,
473 -1132, 504, -24, -352, 324, 332, -600, -312, 292, 508, -144,
474 -8, 484, 48, 284, -260, -240, 256, -100, -292, -204, -44,
475 472, -204, 908, -188, -1000, -256, 92, 1164, -392, 564, 356,
476 652, -28, -884, 256, 484, -192, 760, -176, 376, -524, -452,
477 -436, 860, -736, 212, 124, 504, -476, 468, 76, -472, 552,
478 -692, -944, -620, 740, -240, 400, 132, 20, 192, -196, 264,
479 -668, -1012, -60, 296, -316, -828, 76, -156, 284, -768, -448,
480 -832, 148, 248, 652, 616, 1236, 288, -328, -400, -124, 588,
481 220, 520, -696, 1032, 768, -740, -92, -272, 296, 448, -464,
482 412, -200, 392, 440, -200, 264, -152, -260, 320, 1032, 216,
483 320, -8, -64, 156, -1016, 1084, 1172, 536, 484, -432, 132,
484 372, -52, -256, 84, 116, -352, 48, 116, 304, -384, 412,
485 924, -300, 528, 628, 180, 648, 44, -980, -220, 1320, 48,
486 332, 748, 524, -268, -720, 540, -276, 564, -344, -208, -196,
487 436, 896, 88, -392, 132, 80, -964, -288, 568, 56, -48,
488 -456, 888, 8, 552, -156, -292, 948, 288, 128, -716, -292,
489 1192, -152, 876, 352, -600, -260, -812, -468, -28, -120, -32,
490 -44, 1284, 496, 192, 464, 312, -76, -516, -380, -456, -1012,
491 -48, 308, -156, 36, 492, -156, -808, 188, 1652, 68, -120,
492 -116, 316, 160, -140, 352, 808, -416, 592, 316, -480, 56,
493 528, -204, -568, 372, -232, 752, -344, 744, -4, 324, -416,
494 -600, 768, 268, -248, -88, -132, -420, -432, 80, -288, 404,
495 -316, -1216, -588, 520, -108, 92, -320, 368, -480, -216, -92,
496 1688, -300, 180, 1020, -176, 820, -68, -228, -260, 436, -904,
497 20, 40, -508, 440, -736, 312, 332, 204, 760, -372, 728,
498 96, -20, -632, -520, -560, 336, 1076, -64, -532, 776, 584,
499 192, 396, -728, -520, 276, -188, 80, -52, -612, -252, -48,
500 648, 212, -688, 228, -52, -260, 428, -412, -272, -404, 180,
501 816, -796, 48, 152, 484, -88, -216, 988, 696, 188, -528,
502 648, -116, -180, 316, 476, 12, -564, 96, 476, -252, -364,
503 -376, -392, 556, -256, -576, 260, -352, 120, -16, -136, -260,
504 -492, 72, 556, 660, 580, 616, 772, 436, 424, -32, -324,
505 -1268, 416, -324, -80, 920, 160, 228, 724, 32, -516, 64,
506 384, 68, -128, 136, 240, 248, -204, -68, 252, -932, -120,
507 -480, -628, -84, 192, 852, -404, -288, -132, 204, 100, 168,
508 -68, -196, -868, 460, 1080, 380, -80, 244, 0, 484, -888,
509 64, 184, 352, 600, 460, 164, 604, -196, 320, -64, 588,
510 -184, 228, 12, 372, 48, -848, -344, 224, 208, -200, 484,
511 128, -20, 272, -468, -840, 384, 256, -720, -520, -464, -580,
512 112, -120, 644, -356, -208, -608, -528, 704, 560, -424, 392,
513 828, 40, 84, 200, -152, 0, -144, 584, 280, -120, 80,
514 -556, -972, -196, -472, 724, 80, 168, -32, 88, 160, -688,
515 0, 160, 356, 372, -776, 740, -128, 676, -248, -480, 4,
516 -364, 96, 544, 232, -1032, 956, 236, 356, 20, -40, 300,
517 24, -676, -596, 132, 1120, -104, 532, -1096, 568, 648, 444,
518 508, 380, 188, -376, -604, 1488, 424, 24, 756, -220, -192,
519 716, 120, 920, 688, 168, 44, -460, 568, 284, 1144, 1160,
520 600, 424, 888, 656, -356, -320, 220, 316, -176, -724, -188,
521 -816, -628, -348, -228, -380, 1012, -452, -660, 736, 928, 404,
522 -696, -72, -268, -892, 128, 184, -344, -780, 360, 336, 400,
523 344, 428, 548, -112, 136, -228, -216, -820, -516, 340, 92,
524 -136, 116, -300, 376, -244, 100, -316, -520, -284, -12, 824,
525 164, -548, -180, -128, 116, -924, -828, 268, -368, -580, 620,
526 192, 160, 0, -1676, 1068, 424, -56, -360, 468, -156, 720,
527 288, -528, 556, -364, 548, -148, 504, 316, 152, -648, -620,
528 -684, -24, -376, -384, -108, -920, -1032, 768, 180, -264, -508,
529 -1268, -260, -60, 300, -240, 988, 724, -376, -576, -212, -736,
530 556, 192, 1092, -620, -880, 376, -56, -4, -216, -32, 836,
531 268, 396, 1332, 864, -600, 100, 56, -412, -92, 356, 180,
532 884, -468, -436, 292, -388, -804, -704, -840, 368, -348, 140,
533 -724, 1536, 940, 372, 112, -372, 436, -480, 1136, 296, -32,
534 -228, 132, -48, -220, 868, -1016, -60, -1044, -464, 328, 916,
535 244, 12, -736, -296, 360, 468, -376, -108, -92, 788, 368,
536 -56, 544, 400, -672, -420, 728, 16, 320, 44, -284, -380,
537 -796, 488, 132, 204, -596, -372, 88, -152, -908, -636, -572,
538 -624, -116, -692, -200, -56, 276, -88, 484, -324, 948, 864,
539 1000, -456, -184, -276, 292, -296, 156, 676, 320, 160, 908,
540 -84, -1236, -288, -116, 260, -372, -644, 732, -756, -96, 84,
541 344, -520, 348, -688, 240, -84, 216, -1044, -136, -676, -396,
542 -1500, 960, -40, 176, 168, 1516, 420, -504, -344, -364, -360,
543 1216, -940, -380, -212, 252, -660, -708, 484, -444, -152, 928,
544 -120, 1112, 476, -260, 560, -148, -344, 108, -196, 228, -288,
545 504, 560, -328, -88, 288, -1008, 460, -228, 468, -836, -196,
546 76, 388, 232, 412, -1168, -716, -644, 756, -172, -356, -504,
547 116, 432, 528, 48, 476, -168, -608, 448, 160, -532, -272,
548 28, -676, -12, 828, 980, 456, 520, 104, -104, 256, -344,
549 -4, -28, -368, -52, -524, -572, -556, -200, 768, 1124, -208,
550 -512, 176, 232, 248, -148, -888, 604, -600, -304, 804, -156,
551 -212, 488, -192, -804, -256, 368, -360, -916, -328, 228, -240,
552 -448, -472, 856, -556, -364, 572, -12, -156, -368, -340, 432,
553 252, -752, -152, 288, 268, -580, -848, -592, 108, -76, 244,
554 312, -716, 592, -80, 436, 360, 4, -248, 160, 516, 584,
555 732, 44, -468, -280, -292, -156, -588, 28, 308, 912, 24,
556 124, 156, 180, -252, 944, -924, -772, -520, -428, -624, 300,
557 -212, -1144, 32, -724, 800, -1128, -212, -1288, -848, 180, -416,
558 440, 192, -576, -792, -76, -1080, 80, -532, -352, -132, 380,
559 -820, 148, 1112, 128, 164, 456, 700, -924, 144, -668, -384,
560 648, -832, 508, 552, -52, -100, -656, 208, -568, 748, -88,
561 680, 232, 300, 192, -408, -1012, -152, -252, -268, 272, -876,
562 -664, -648, -332, -136, 16, 12, 1152, -28, 332, -536, 320,
563 -672, -460, -316, 532, -260, 228, -40, 1052, -816, 180, 88,
564 -496, -556, -672, -368, 428, 92, 356, 404, -408, 252, 196,
565 -176, -556, 792, 268, 32, 372, 40, 96, -332, 328, 120,
566 372, -900, -40, 472, -264, -592, 952, 128, 656, 112, 664,
567 -232, 420, 4, -344, -464, 556, 244, -416, -32, 252, 0,
568 -412, 188, -696, 508, -476, 324, -1096, 656, -312, 560, 264,
569 -136, 304, 160, -64, -580, 248, 336, -720, 560, -348, -288,
570 -276, -196, -500, 852, -544, -236, -1128, -992, -776, 116, 56,
571 52, 860, 884, 212, -12, 168, 1020, 512, -552, 924, -148,
572 716, 188, 164, -340, -520, -184, 880, -152, -680, -208, -1156,
573 -300, -528, -472, 364, 100, -744, -1056, -32, 540, 280, 144,
574 -676, -32, -232, -280, -224, 96, 568, -76, 172, 148, 148,
575 104, 32, -296, -32, 788, -80, 32, -16, 280, 288, 944,
576 428, -484
577 };
578