=== modified file 'grub-core/video/readers/png.c' --- grub-core/video/readers/png.c 2013-09-28 01:04:34 +0000 +++ grub-core/video/readers/png.c 2013-09-28 21:51:16 +0000 @@ -31,7 +31,6 @@ enum { - PNG_COLOR_TYPE_GRAY = 0, PNG_COLOR_MASK_PALETTE = 1, PNG_COLOR_MASK_COLOR = 2, PNG_COLOR_MASK_ALPHA = 4, @@ -40,8 +39,11 @@ #define PNG_COMPRESSION_BASE 0 -#define PNG_INTERLACE_NONE 0 -#define PNG_INTERLACE_ADAM7 1 +enum + { + PNG_INTERLACE_NONE = 0, + PNG_INTERLACE_ADAM7 = 1 + }; #define PNG_FILTER_TYPE_BASE 0 @@ -88,6 +90,28 @@ int num_values, max_length; }; +struct interlace_stage +{ + int start_x, start_y; + int log_step_x, log_step_y; +}; + +static struct interlace_stage interleave_none[] = + { + { 0, 0, 0, 0 } + }; + +static struct interlace_stage interleave_adam7[] = + { + { 0, 0, 3, 3 }, + { 4, 0, 3, 3 }, + { 0, 4, 2, 3 }, + { 2, 0, 2, 2 }, + { 0, 2, 1, 2 }, + { 1, 0, 1, 1 }, + { 0, 1, 0, 1 } + }; + struct grub_png_data { grub_file_t file; @@ -99,6 +123,8 @@ int image_width, image_height, bpp, is_16bit; int raw_bytes, is_gray, is_alpha, is_palette; + int row_bytes, row_bytes_i, row_bytes_i2, color_bits; + int skip; grub_uint8_t *image_data; int inside_idat, idat_remain; @@ -119,9 +145,15 @@ grub_uint8_t slide[WSIZE]; int wp; - grub_uint8_t *cur_rgb; + grub_uint8_t *cur_rgb, *rgb0; int cur_column, cur_filter, first_line; + int cur_component; + + struct interlace_stage *cur_interleave; + int n_interleave; + + int is_adam7; }; static grub_uint32_t @@ -245,6 +277,7 @@ int color_type; int color_bits; enum grub_video_blit_format blt; + grub_uint8_t interleave; data->image_width = grub_png_get_dword (data); data->image_height = grub_png_get_dword (data); @@ -253,9 +286,6 @@ return grub_error (GRUB_ERR_BAD_FILE_TYPE, "png: invalid image size"); color_bits = grub_png_get_byte (data); - if ((color_bits != 8) && (color_bits != 16)) - return grub_error (GRUB_ERR_BAD_FILE_TYPE, - "png: bit depth must be 8 or 16"); data->is_16bit = (color_bits == 16); color_type = grub_png_get_byte (data); @@ -283,6 +313,13 @@ data->bpp = 1; } + if ((color_bits != 8) && (color_bits != 16) + && ((color_bits != 4 && color_bits != 2 + && color_bits != 1) + || !(data->is_gray || data->is_palette))) + return grub_error (GRUB_ERR_BAD_FILE_TYPE, + "png: bit depth must be 8 or 16"); + if (color_type & PNG_COLOR_MASK_ALPHA) data->bpp++; @@ -294,30 +331,29 @@ if (data->is_16bit) data->bpp <<= 1; + data->color_bits = color_bits; + data->row_bytes = data->image_width * data->bpp; + if (data->color_bits <= 4) + data->row_bytes = (data->image_width * data->color_bits + 7) / 8 + 16; + #ifndef GRUB_CPU_WORDS_BIGENDIAN if (data->is_16bit || data->is_gray || data->is_palette) #endif { - data->image_data = grub_malloc (data->image_height * - data->image_width * data->bpp); + data->image_data = grub_malloc (data->image_height * data->row_bytes); if (grub_errno) return grub_errno; - data->cur_rgb = data->image_data; + data->rgb0 = data->image_data; } #ifndef GRUB_CPU_WORDS_BIGENDIAN else { data->image_data = 0; - data->cur_rgb = (*data->bitmap)->data; + data->rgb0 = (*data->bitmap)->data; } #endif - data->raw_bytes = data->image_height * (data->image_width * data->bpp + 1); - - data->cur_column = 0; - data->first_line = 1; - if (grub_png_get_byte (data) != PNG_COMPRESSION_BASE) return grub_error (GRUB_ERR_BAD_FILE_TYPE, "png: compression method not supported"); @@ -326,9 +362,22 @@ return grub_error (GRUB_ERR_BAD_FILE_TYPE, "png: filter method not supported"); - if (grub_png_get_byte (data) != PNG_INTERLACE_NONE) - return grub_error (GRUB_ERR_BAD_FILE_TYPE, - "png: interlace method not supported"); + interleave = grub_png_get_byte (data); + switch (interleave) + { + case PNG_INTERLACE_NONE: + data->cur_interleave = interleave_none - 1; + data->n_interleave = ARRAY_SIZE (interleave_none); + break; + case PNG_INTERLACE_ADAM7: + data->cur_interleave = interleave_adam7 - 1; + data->n_interleave = ARRAY_SIZE (interleave_adam7); + data->is_adam7 = 1; + break; + default: + return grub_error (GRUB_ERR_BAD_FILE_TYPE, + "png: interlace method not supported"); + } /* Skip crc checksum. */ grub_png_get_dword (data); @@ -567,104 +616,189 @@ static grub_err_t grub_png_output_byte (struct grub_png_data *data, grub_uint8_t n) { - int row_bytes; - - if (--data->raw_bytes < 0) + while (data->raw_bytes == 0 && data->n_interleave) + { + int rows_i; + data->cur_interleave++; + + data->cur_rgb = data->rgb0; + + rows_i = (data->image_width >> data->cur_interleave->log_step_x); + if (data->color_bits <= 4) + { + data->row_bytes_i = (rows_i * data->color_bits + 7) / 8; + data->skip = ((1 << data->cur_interleave->log_step_x) - 1); + data->cur_rgb += data->cur_interleave->start_x; + } + else + { + data->row_bytes_i = rows_i * data->bpp; + + data->skip = ((1 << data->cur_interleave->log_step_x) - 1) * data->bpp; + data->cur_rgb += data->cur_interleave->start_x * data->bpp; + } + + data->row_bytes_i2 = data->row_bytes_i + + data->skip * (data->row_bytes_i / data->bpp); + + data->raw_bytes = (data->image_height >> data->cur_interleave->log_step_y) + * (data->row_bytes_i + 1); + + data->cur_column = 0; + data->cur_filter = 0; + data->first_line = 1; + data->cur_component = 0; + data->cur_rgb += data->cur_interleave->start_y * data->row_bytes; + data->n_interleave--; + } + + data->raw_bytes--; + + if (data->raw_bytes < 0) return grub_error (GRUB_ERR_BAD_FILE_TYPE, "image size overflown"); if (data->cur_column == 0) { if (n >= PNG_FILTER_VALUE_LAST) - return grub_error (GRUB_ERR_BAD_FILE_TYPE, "invalid filter value"); + return grub_error (GRUB_ERR_BAD_FILE_TYPE, "invalid filter value %d", n); data->cur_filter = n; + if (!data->first_line) + data->cur_rgb += (1 << data->cur_interleave->log_step_y) + * data->row_bytes - data->row_bytes_i2; } else - *data->cur_rgb++ = n; + { + *data->cur_rgb++ = n; + data->cur_component++; + if (data->cur_component == data->bpp) + { + data->cur_component = 0; + data->cur_rgb += data->skip; + } + } data->cur_column++; - row_bytes = data->image_width * data->bpp; - if (data->cur_column == row_bytes + 1) + + if (data->cur_column == data->row_bytes_i + 1) { grub_uint8_t *blank_line = NULL; - grub_uint8_t *cur = data->cur_rgb - row_bytes; + grub_uint8_t *cur = data->cur_rgb - data->row_bytes_i2; grub_uint8_t *left = cur; grub_uint8_t *up; if (data->first_line) { - blank_line = grub_zalloc (row_bytes); + blank_line = grub_zalloc (data->row_bytes); if (blank_line == NULL) return grub_errno; up = blank_line; } else - up = cur - row_bytes; + up = cur - (data->row_bytes << data->cur_interleave->log_step_y); switch (data->cur_filter) { case PNG_FILTER_VALUE_SUB: { - int i; + int i, j; - cur += data->bpp; - for (i = data->bpp; i < row_bytes; i++, cur++, left++) - *cur += *left; + cur += data->bpp + data->skip; + for (i = data->bpp; i < data->row_bytes; ) + { + for (j = 0; j < data->bpp; j++) + { + *cur += *left; + i++, cur++, left++; + } + i += data->skip; + cur += data->skip; + left += data->skip; + } break; } case PNG_FILTER_VALUE_UP: { - int i; - - for (i = 0; i < row_bytes; i++, cur++, up++) - *cur += *up; - + int i, j; + + for (i = 0; i < data->row_bytes; ) + { + for (j = 0; j < data->bpp; j++) + { + *cur += *up; + i++, cur++, up++; + } + i += data->skip; + cur += data->skip; + up += data->skip; + } break; } case PNG_FILTER_VALUE_AVG: { - int i; + int i, j; for (i = 0; i < data->bpp; i++, cur++, up++) *cur += *up >> 1; - for (; i < row_bytes; i++, cur++, up++, left++) - *cur += ((int) *up + (int) *left) >> 1; + i += data->skip; + cur += data->skip; + up += data->skip; + + for (; i < data->row_bytes; ) + { + for (j = 0; j < data->bpp; j++) + { + *cur += ((int) *up + (int) *left) >> 1; + i++, cur++, up++, left++; + } + i+= data->skip, cur+= data->skip, up+= data->skip, left+= data->skip; + } break; } case PNG_FILTER_VALUE_PAETH: { - int i; + int i, j; grub_uint8_t *upper_left = up; for (i = 0; i < data->bpp; i++, cur++, up++) *cur += *up; - for (; i < row_bytes; i++, cur++, up++, left++, upper_left++) + i += data->skip; + cur += data->skip; + up += data->skip; + + for (; i < data->row_bytes; ) { - int a, b, c, pa, pb, pc; - - a = *left; - b = *up; - c = *upper_left; - - pa = b - c; - pb = a - c; - pc = pa + pb; - - if (pa < 0) - pa = -pa; - - if (pb < 0) - pb = -pb; - - if (pc < 0) - pc = -pc; - - *cur += ((pa <= pb) && (pa <= pc)) ? a : (pb <= pc) ? b : c; + for (j = 0; j < data->bpp; j++) + { + int a, b, c, pa, pb, pc; + + a = *left; + b = *up; + c = *upper_left; + + pa = b - c; + pb = a - c; + pc = pa + pb; + + if (pa < 0) + pa = -pa; + + if (pb < 0) + pb = -pb; + + if (pc < 0) + pc = -pc; + + *cur += ((pa <= pb) && (pa <= pc)) ? a : (pb <= pc) ? b : c; + i++, cur++, up++, left++, upper_left++; + } + i+=data->skip, cur+=data->skip, up+=data->skip; + left+=data->skip, upper_left+=data->skip; } } } @@ -809,6 +943,8 @@ static const grub_uint8_t png_magic[8] = { 0x89, 0x50, 0x4e, 0x47, 0xd, 0xa, 0x1a, 0x0a }; +#include "png_adam7.c" + static void grub_png_convert_image (struct grub_png_data *data) { @@ -836,6 +972,87 @@ #define B3 2 #endif + if (data->color_bits <= 4) + { + grub_uint8_t palette[16][3]; + grub_uint8_t *dc; + int shift = 8 - data->color_bits; + int mask = (1 << data->color_bits) - 1; + int j; + if (data->is_gray) + for (i = 0; i < (1 << data->color_bits); i++) + { + grub_uint8_t col = (0xff * i) / ((1 << data->color_bits) - 1); + palette[i][0] = col; + palette[i][1] = col; + palette[i][2] = col; + } + else + grub_memcpy (palette, data->palette, 16 * 3); + dc = d2; + /* Our algorithms work on bytes in case of color depth <= 4. + Usually it's no problem as PNG specs does the same. However + Adam7 always works on pixels, so we need this additional shuffling. + */ + if (data->is_adam7) + { + int klen = 16; + if (data->color_bits == 2) + klen = 32; + if (data->color_bits == 1) + klen = 64; + for (j = 0; j < data->image_height; j++) + { + const grub_uint8_t (*remap)[2] = NULL; + int k; + + if (data->color_bits == 4) + remap = adam7_remap_4bit[j%8]; + if (data->color_bits == 2) + remap = adam7_remap_2bit[j%8]; + if (data->color_bits == 1) + remap = adam7_remap_1bit[j%8]; + d2 = dc; + dc += data->row_bytes; + for (i = 0, k = 0; i < data->image_width; + i++, d1 += 3) + { + grub_uint8_t col = (d2[remap[k][0]] >> remap[k][1]) & mask; + d1[R3] = data->palette[col][2]; + d1[G3] = data->palette[col][1]; + d1[B3] = data->palette[col][0]; + k++; + if (k == klen) + { + d2 += 8; + k = 0; + } + } + } + } + else + for (j = 0; j < data->image_height; j++) + { + d2 = dc; + dc += data->row_bytes; + for (i = 0; i < data->image_width; + i++, d1 += 3) + { + grub_uint8_t col = (d2[0] >> shift) & mask; + d1[R3] = data->palette[col][2]; + d1[G3] = data->palette[col][1]; + d1[B3] = data->palette[col][0]; + shift -= data->color_bits; + if (shift < 0) + { + d2++; + shift += 8; + } + } + } + return; + } + if (data->is_palette) { for (i = 0; i < (data->image_width * data->image_height); === added file 'grub-core/video/readers/png_adam7.c' --- grub-core/video/readers/png_adam7.c 1970-01-01 00:00:00 +0000 +++ grub-core/video/readers/png_adam7.c 2013-09-28 21:10:18 +0000 @@ -0,0 +1,171 @@ +static const grub_uint8_t adam7_remap_4bit[8][16][2] = + { + { { 0, 4 }, { 1, 4 }, { 2, 4 }, { 1, 0 }, { 4, 4 }, { 3, 4 }, + { 2, 0 }, { 3, 0 }, { 0, 0 }, { 5, 4 }, { 6, 4 }, { 5, 0 }, + { 4, 0 }, { 7, 4 }, { 6, 0 }, { 7, 0 }, }, + { { 0, 4 }, { 0, 0 }, { 1, 4 }, { 1, 0 }, { 2, 4 }, { 2, 0 }, + { 3, 4 }, { 3, 0 }, { 4, 4 }, { 4, 0 }, { 5, 4 }, { 5, 0 }, + { 6, 4 }, { 6, 0 }, { 7, 4 }, { 7, 0 }, }, + { { 0, 4 }, { 1, 4 }, { 0, 0 }, { 1, 0 }, { 2, 4 }, { 3, 4 }, + { 2, 0 }, { 3, 0 }, { 4, 4 }, { 5, 4 }, { 4, 0 }, { 5, 0 }, + { 6, 4 }, { 7, 4 }, { 6, 0 }, { 7, 0 }, }, + { { 0, 4 }, { 0, 0 }, { 1, 4 }, { 1, 0 }, { 2, 4 }, { 2, 0 }, + { 3, 4 }, { 3, 0 }, { 4, 4 }, { 4, 0 }, { 5, 4 }, { 5, 0 }, + { 6, 4 }, { 6, 0 }, { 7, 4 }, { 7, 0 }, }, + { { 0, 4 }, { 1, 4 }, { 2, 4 }, { 1, 0 }, { 0, 0 }, { 3, 4 }, + { 2, 0 }, { 3, 0 }, { 4, 4 }, { 5, 4 }, { 6, 4 }, { 5, 0 }, + { 4, 0 }, { 7, 4 }, { 6, 0 }, { 7, 0 }, }, + { { 0, 4 }, { 0, 0 }, { 1, 4 }, { 1, 0 }, { 2, 4 }, { 2, 0 }, + { 3, 4 }, { 3, 0 }, { 4, 4 }, { 4, 0 }, { 5, 4 }, { 5, 0 }, + { 6, 4 }, { 6, 0 }, { 7, 4 }, { 7, 0 }, }, + { { 0, 4 }, { 1, 4 }, { 0, 0 }, { 1, 0 }, { 2, 4 }, { 3, 4 }, + { 2, 0 }, { 3, 0 }, { 4, 4 }, { 5, 4 }, { 4, 0 }, { 5, 0 }, + { 6, 4 }, { 7, 4 }, { 6, 0 }, { 7, 0 }, }, + { { 0, 4 }, { 0, 0 }, { 1, 4 }, { 1, 0 }, { 2, 4 }, { 2, 0 }, + { 3, 4 }, { 3, 0 }, { 4, 4 }, { 4, 0 }, { 5, 4 }, { 5, 0 }, + { 6, 4 }, { 6, 0 }, { 7, 4 }, { 7, 0 }, }, + }; + +static const grub_uint8_t adam7_remap_2bit[8][32][2] = + { + { { 0, 6 }, { 1, 6 }, { 2, 6 }, { 1, 4 }, { 4, 6 }, { 1, 2 }, + { 2, 4 }, { 1, 0 }, { 0, 4 }, { 3, 6 }, { 2, 2 }, { 3, 4 }, + { 4, 4 }, { 3, 2 }, { 2, 0 }, { 3, 0 }, { 0, 2 }, { 5, 6 }, + { 6, 6 }, { 5, 4 }, { 4, 2 }, { 5, 2 }, { 6, 4 }, { 5, 0 }, + { 0, 0 }, { 7, 6 }, { 6, 2 }, { 7, 4 }, { 4, 0 }, { 7, 2 }, + { 6, 0 }, { 7, 0 }, }, + { { 0, 6 }, { 0, 4 }, { 0, 2 }, { 0, 0 }, { 1, 6 }, { 1, 4 }, + { 1, 2 }, { 1, 0 }, { 2, 6 }, { 2, 4 }, { 2, 2 }, { 2, 0 }, + { 3, 6 }, { 3, 4 }, { 3, 2 }, { 3, 0 }, { 4, 6 }, { 4, 4 }, + { 4, 2 }, { 4, 0 }, { 5, 6 }, { 5, 4 }, { 5, 2 }, { 5, 0 }, + { 6, 6 }, { 6, 4 }, { 6, 2 }, { 6, 0 }, { 7, 6 }, { 7, 4 }, + { 7, 2 }, { 7, 0 }, }, + { { 0, 6 }, { 1, 6 }, { 0, 4 }, { 1, 4 }, { 0, 2 }, { 1, 2 }, + { 0, 0 }, { 1, 0 }, { 2, 6 }, { 3, 6 }, { 2, 4 }, { 3, 4 }, + { 2, 2 }, { 3, 2 }, { 2, 0 }, { 3, 0 }, { 4, 6 }, { 5, 6 }, + { 4, 4 }, { 5, 4 }, { 4, 2 }, { 5, 2 }, { 4, 0 }, { 5, 0 }, + { 6, 6 }, { 7, 6 }, { 6, 4 }, { 7, 4 }, { 6, 2 }, { 7, 2 }, + { 6, 0 }, { 7, 0 }, }, + { { 0, 6 }, { 0, 4 }, { 0, 2 }, { 0, 0 }, { 1, 6 }, { 1, 4 }, + { 1, 2 }, { 1, 0 }, { 2, 6 }, { 2, 4 }, { 2, 2 }, { 2, 0 }, + { 3, 6 }, { 3, 4 }, { 3, 2 }, { 3, 0 }, { 4, 6 }, { 4, 4 }, + { 4, 2 }, { 4, 0 }, { 5, 6 }, { 5, 4 }, { 5, 2 }, { 5, 0 }, + { 6, 6 }, { 6, 4 }, { 6, 2 }, { 6, 0 }, { 7, 6 }, { 7, 4 }, + { 7, 2 }, { 7, 0 }, }, + { { 0, 6 }, { 1, 6 }, { 2, 6 }, { 1, 4 }, { 0, 4 }, { 1, 2 }, + { 2, 4 }, { 1, 0 }, { 0, 2 }, { 3, 6 }, { 2, 2 }, { 3, 4 }, + { 0, 0 }, { 3, 2 }, { 2, 0 }, { 3, 0 }, { 4, 6 }, { 5, 6 }, + { 6, 6 }, { 5, 4 }, { 4, 4 }, { 5, 2 }, { 6, 4 }, { 5, 0 }, + { 4, 2 }, { 7, 6 }, { 6, 2 }, { 7, 4 }, { 4, 0 }, { 7, 2 }, + { 6, 0 }, { 7, 0 }, }, + { { 0, 6 }, { 0, 4 }, { 0, 2 }, { 0, 0 }, { 1, 6 }, { 1, 4 }, + { 1, 2 }, { 1, 0 }, { 2, 6 }, { 2, 4 }, { 2, 2 }, { 2, 0 }, + { 3, 6 }, { 3, 4 }, { 3, 2 }, { 3, 0 }, { 4, 6 }, { 4, 4 }, + { 4, 2 }, { 4, 0 }, { 5, 6 }, { 5, 4 }, { 5, 2 }, { 5, 0 }, + { 6, 6 }, { 6, 4 }, { 6, 2 }, { 6, 0 }, { 7, 6 }, { 7, 4 }, + { 7, 2 }, { 7, 0 }, }, + { { 0, 6 }, { 1, 6 }, { 0, 4 }, { 1, 4 }, { 0, 2 }, { 1, 2 }, + { 0, 0 }, { 1, 0 }, { 2, 6 }, { 3, 6 }, { 2, 4 }, { 3, 4 }, + { 2, 2 }, { 3, 2 }, { 2, 0 }, { 3, 0 }, { 4, 6 }, { 5, 6 }, + { 4, 4 }, { 5, 4 }, { 4, 2 }, { 5, 2 }, { 4, 0 }, { 5, 0 }, + { 6, 6 }, { 7, 6 }, { 6, 4 }, { 7, 4 }, { 6, 2 }, { 7, 2 }, + { 6, 0 }, { 7, 0 }, }, + { { 0, 6 }, { 0, 4 }, { 0, 2 }, { 0, 0 }, { 1, 6 }, { 1, 4 }, + { 1, 2 }, { 1, 0 }, { 2, 6 }, { 2, 4 }, { 2, 2 }, { 2, 0 }, + { 3, 6 }, { 3, 4 }, { 3, 2 }, { 3, 0 }, { 4, 6 }, { 4, 4 }, + { 4, 2 }, { 4, 0 }, { 5, 6 }, { 5, 4 }, { 5, 2 }, { 5, 0 }, + { 6, 6 }, { 6, 4 }, { 6, 2 }, { 6, 0 }, { 7, 6 }, { 7, 4 }, + { 7, 2 }, { 7, 0 }, }, + }; + +static const grub_uint8_t adam7_remap_1bit[8][64][2] = + { + { { 0, 7 }, { 1, 7 }, { 2, 7 }, { 1, 6 }, { 4, 7 }, { 1, 5 }, + { 2, 6 }, { 1, 4 }, { 0, 6 }, { 1, 3 }, { 2, 5 }, { 1, 2 }, + { 4, 6 }, { 1, 1 }, { 2, 4 }, { 1, 0 }, { 0, 5 }, { 3, 7 }, + { 2, 3 }, { 3, 6 }, { 4, 5 }, { 3, 5 }, { 2, 2 }, { 3, 4 }, + { 0, 4 }, { 3, 3 }, { 2, 1 }, { 3, 2 }, { 4, 4 }, { 3, 1 }, + { 2, 0 }, { 3, 0 }, { 0, 3 }, { 5, 7 }, { 6, 7 }, { 5, 6 }, + { 4, 3 }, { 5, 5 }, { 6, 6 }, { 5, 4 }, { 0, 2 }, { 5, 3 }, + { 6, 5 }, { 5, 2 }, { 4, 2 }, { 5, 1 }, { 6, 4 }, { 5, 0 }, + { 0, 1 }, { 7, 7 }, { 6, 3 }, { 7, 6 }, { 4, 1 }, { 7, 5 }, + { 6, 2 }, { 7, 4 }, { 0, 0 }, { 7, 3 }, { 6, 1 }, { 7, 2 }, + { 4, 0 }, { 7, 1 }, { 6, 0 }, { 7, 0 }, }, + { { 0, 7 }, { 0, 6 }, { 0, 5 }, { 0, 4 }, { 0, 3 }, { 0, 2 }, + { 0, 1 }, { 0, 0 }, { 1, 7 }, { 1, 6 }, { 1, 5 }, { 1, 4 }, + { 1, 3 }, { 1, 2 }, { 1, 1 }, { 1, 0 }, { 2, 7 }, { 2, 6 }, + { 2, 5 }, { 2, 4 }, { 2, 3 }, { 2, 2 }, { 2, 1 }, { 2, 0 }, + { 3, 7 }, { 3, 6 }, { 3, 5 }, { 3, 4 }, { 3, 3 }, { 3, 2 }, + { 3, 1 }, { 3, 0 }, { 4, 7 }, { 4, 6 }, { 4, 5 }, { 4, 4 }, + { 4, 3 }, { 4, 2 }, { 4, 1 }, { 4, 0 }, { 5, 7 }, { 5, 6 }, + { 5, 5 }, { 5, 4 }, { 5, 3 }, { 5, 2 }, { 5, 1 }, { 5, 0 }, + { 6, 7 }, { 6, 6 }, { 6, 5 }, { 6, 4 }, { 6, 3 }, { 6, 2 }, + { 6, 1 }, { 6, 0 }, { 7, 7 }, { 7, 6 }, { 7, 5 }, { 7, 4 }, + { 7, 3 }, { 7, 2 }, { 7, 1 }, { 7, 0 }, }, + { { 0, 7 }, { 1, 7 }, { 0, 6 }, { 1, 6 }, { 0, 5 }, { 1, 5 }, + { 0, 4 }, { 1, 4 }, { 0, 3 }, { 1, 3 }, { 0, 2 }, { 1, 2 }, + { 0, 1 }, { 1, 1 }, { 0, 0 }, { 1, 0 }, { 2, 7 }, { 3, 7 }, + { 2, 6 }, { 3, 6 }, { 2, 5 }, { 3, 5 }, { 2, 4 }, { 3, 4 }, + { 2, 3 }, { 3, 3 }, { 2, 2 }, { 3, 2 }, { 2, 1 }, { 3, 1 }, + { 2, 0 }, { 3, 0 }, { 4, 7 }, { 5, 7 }, { 4, 6 }, { 5, 6 }, + { 4, 5 }, { 5, 5 }, { 4, 4 }, { 5, 4 }, { 4, 3 }, { 5, 3 }, + { 4, 2 }, { 5, 2 }, { 4, 1 }, { 5, 1 }, { 4, 0 }, { 5, 0 }, + { 6, 7 }, { 7, 7 }, { 6, 6 }, { 7, 6 }, { 6, 5 }, { 7, 5 }, + { 6, 4 }, { 7, 4 }, { 6, 3 }, { 7, 3 }, { 6, 2 }, { 7, 2 }, + { 6, 1 }, { 7, 1 }, { 6, 0 }, { 7, 0 }, }, + { { 0, 7 }, { 0, 6 }, { 0, 5 }, { 0, 4 }, { 0, 3 }, { 0, 2 }, + { 0, 1 }, { 0, 0 }, { 1, 7 }, { 1, 6 }, { 1, 5 }, { 1, 4 }, + { 1, 3 }, { 1, 2 }, { 1, 1 }, { 1, 0 }, { 2, 7 }, { 2, 6 }, + { 2, 5 }, { 2, 4 }, { 2, 3 }, { 2, 2 }, { 2, 1 }, { 2, 0 }, + { 3, 7 }, { 3, 6 }, { 3, 5 }, { 3, 4 }, { 3, 3 }, { 3, 2 }, + { 3, 1 }, { 3, 0 }, { 4, 7 }, { 4, 6 }, { 4, 5 }, { 4, 4 }, + { 4, 3 }, { 4, 2 }, { 4, 1 }, { 4, 0 }, { 5, 7 }, { 5, 6 }, + { 5, 5 }, { 5, 4 }, { 5, 3 }, { 5, 2 }, { 5, 1 }, { 5, 0 }, + { 6, 7 }, { 6, 6 }, { 6, 5 }, { 6, 4 }, { 6, 3 }, { 6, 2 }, + { 6, 1 }, { 6, 0 }, { 7, 7 }, { 7, 6 }, { 7, 5 }, { 7, 4 }, + { 7, 3 }, { 7, 2 }, { 7, 1 }, { 7, 0 }, }, + { { 0, 7 }, { 1, 7 }, { 2, 7 }, { 1, 6 }, { 0, 6 }, { 1, 5 }, + { 2, 6 }, { 1, 4 }, { 0, 5 }, { 1, 3 }, { 2, 5 }, { 1, 2 }, + { 0, 4 }, { 1, 1 }, { 2, 4 }, { 1, 0 }, { 0, 3 }, { 3, 7 }, + { 2, 3 }, { 3, 6 }, { 0, 2 }, { 3, 5 }, { 2, 2 }, { 3, 4 }, + { 0, 1 }, { 3, 3 }, { 2, 1 }, { 3, 2 }, { 0, 0 }, { 3, 1 }, + { 2, 0 }, { 3, 0 }, { 4, 7 }, { 5, 7 }, { 6, 7 }, { 5, 6 }, + { 4, 6 }, { 5, 5 }, { 6, 6 }, { 5, 4 }, { 4, 5 }, { 5, 3 }, + { 6, 5 }, { 5, 2 }, { 4, 4 }, { 5, 1 }, { 6, 4 }, { 5, 0 }, + { 4, 3 }, { 7, 7 }, { 6, 3 }, { 7, 6 }, { 4, 2 }, { 7, 5 }, + { 6, 2 }, { 7, 4 }, { 4, 1 }, { 7, 3 }, { 6, 1 }, { 7, 2 }, + { 4, 0 }, { 7, 1 }, { 6, 0 }, { 7, 0 }, }, + { { 0, 7 }, { 0, 6 }, { 0, 5 }, { 0, 4 }, { 0, 3 }, { 0, 2 }, + { 0, 1 }, { 0, 0 }, { 1, 7 }, { 1, 6 }, { 1, 5 }, { 1, 4 }, + { 1, 3 }, { 1, 2 }, { 1, 1 }, { 1, 0 }, { 2, 7 }, { 2, 6 }, + { 2, 5 }, { 2, 4 }, { 2, 3 }, { 2, 2 }, { 2, 1 }, { 2, 0 }, + { 3, 7 }, { 3, 6 }, { 3, 5 }, { 3, 4 }, { 3, 3 }, { 3, 2 }, + { 3, 1 }, { 3, 0 }, { 4, 7 }, { 4, 6 }, { 4, 5 }, { 4, 4 }, + { 4, 3 }, { 4, 2 }, { 4, 1 }, { 4, 0 }, { 5, 7 }, { 5, 6 }, + { 5, 5 }, { 5, 4 }, { 5, 3 }, { 5, 2 }, { 5, 1 }, { 5, 0 }, + { 6, 7 }, { 6, 6 }, { 6, 5 }, { 6, 4 }, { 6, 3 }, { 6, 2 }, + { 6, 1 }, { 6, 0 }, { 7, 7 }, { 7, 6 }, { 7, 5 }, { 7, 4 }, + { 7, 3 }, { 7, 2 }, { 7, 1 }, { 7, 0 }, }, + { { 0, 7 }, { 1, 7 }, { 0, 6 }, { 1, 6 }, { 0, 5 }, { 1, 5 }, + { 0, 4 }, { 1, 4 }, { 0, 3 }, { 1, 3 }, { 0, 2 }, { 1, 2 }, + { 0, 1 }, { 1, 1 }, { 0, 0 }, { 1, 0 }, { 2, 7 }, { 3, 7 }, + { 2, 6 }, { 3, 6 }, { 2, 5 }, { 3, 5 }, { 2, 4 }, { 3, 4 }, + { 2, 3 }, { 3, 3 }, { 2, 2 }, { 3, 2 }, { 2, 1 }, { 3, 1 }, + { 2, 0 }, { 3, 0 }, { 4, 7 }, { 5, 7 }, { 4, 6 }, { 5, 6 }, + { 4, 5 }, { 5, 5 }, { 4, 4 }, { 5, 4 }, { 4, 3 }, { 5, 3 }, + { 4, 2 }, { 5, 2 }, { 4, 1 }, { 5, 1 }, { 4, 0 }, { 5, 0 }, + { 6, 7 }, { 7, 7 }, { 6, 6 }, { 7, 6 }, { 6, 5 }, { 7, 5 }, + { 6, 4 }, { 7, 4 }, { 6, 3 }, { 7, 3 }, { 6, 2 }, { 7, 2 }, + { 6, 1 }, { 7, 1 }, { 6, 0 }, { 7, 0 }, }, + { { 0, 7 }, { 0, 6 }, { 0, 5 }, { 0, 4 }, { 0, 3 }, { 0, 2 }, + { 0, 1 }, { 0, 0 }, { 1, 7 }, { 1, 6 }, { 1, 5 }, { 1, 4 }, + { 1, 3 }, { 1, 2 }, { 1, 1 }, { 1, 0 }, { 2, 7 }, { 2, 6 }, + { 2, 5 }, { 2, 4 }, { 2, 3 }, { 2, 2 }, { 2, 1 }, { 2, 0 }, + { 3, 7 }, { 3, 6 }, { 3, 5 }, { 3, 4 }, { 3, 3 }, { 3, 2 }, + { 3, 1 }, { 3, 0 }, { 4, 7 }, { 4, 6 }, { 4, 5 }, { 4, 4 }, + { 4, 3 }, { 4, 2 }, { 4, 1 }, { 4, 0 }, { 5, 7 }, { 5, 6 }, + { 5, 5 }, { 5, 4 }, { 5, 3 }, { 5, 2 }, { 5, 1 }, { 5, 0 }, + { 6, 7 }, { 6, 6 }, { 6, 5 }, { 6, 4 }, { 6, 3 }, { 6, 2 }, + { 6, 1 }, { 6, 0 }, { 7, 7 }, { 7, 6 }, { 7, 5 }, { 7, 4 }, + { 7, 3 }, { 7, 2 }, { 7, 1 }, { 7, 0 }, }, + };