avcodec/gif: support crop and transparency with PAL8
authorClément Bœsch <u@pkh.me>
Sat, 24 Jan 2015 20:36:47 +0000 (21:36 +0100)
committerClément Bœsch <u@pkh.me>
Sat, 14 Feb 2015 19:48:50 +0000 (20:48 +0100)
libavcodec/gif.c
tests/ref/fate/gifenc-pal8

index 27d054e..12a039e 100644 (file)
@@ -46,6 +46,9 @@ typedef struct {
     AVFrame *last_frame;
     int flags;
     uint32_t palette[AVPALETTE_COUNT];  ///< local reference palette for !pal8
+    int palette_loaded;
+    int transparent_index;
+    uint8_t *pal_exdata;
     uint8_t *tmpl;                      ///< temporary line buffer
 } GIFContext;
 
@@ -78,11 +81,11 @@ static int gif_image_write_image(AVCodecContext *avctx,
 {
     GIFContext *s = avctx->priv_data;
     int len = 0, height = avctx->height, width = avctx->width, x, y;
-    int x_start = 0, y_start = 0, trans = -1;
+    int x_start = 0, y_start = 0, trans = s->transparent_index;
+    int honor_transparency = (s->flags & GF_TRANSDIFF) && s->last_frame;
     const uint8_t *ptr;
 
     /* Crop image */
-    // TODO support with palette change
     if ((s->flags & GF_OFFSETTING) && s->last_frame && !palette) {
         const uint8_t *ref = s->last_frame->data[0];
         const int ref_linesize = s->last_frame->linesize[0];
@@ -151,20 +154,23 @@ static int gif_image_write_image(AVCodecContext *avctx,
         }
     }
 
-    /* TODO: support with palette change (pal8) */
-    if ((s->flags & GF_TRANSDIFF) && s->last_frame && !palette) {
+    if (honor_transparency && trans < 0) {
         trans = pick_palette_entry(buf + y_start*linesize + x_start,
                                    linesize, width, height);
         if (trans < 0) { // TODO, patch welcome
             av_log(avctx, AV_LOG_DEBUG, "No available color, can not use transparency\n");
         } else {
-            uint8_t *pal_exdata = av_packet_new_side_data(pkt, AV_PKT_DATA_PALETTE, AVPALETTE_SIZE);
+            uint8_t *pal_exdata = s->pal_exdata;
+            if (!pal_exdata)
+                pal_exdata = av_packet_new_side_data(pkt, AV_PKT_DATA_PALETTE, AVPALETTE_SIZE);
             if (!pal_exdata)
                 return AVERROR(ENOMEM);
             memcpy(pal_exdata, s->palette, AVPALETTE_SIZE);
             pal_exdata[trans*4 + 3*!HAVE_BIGENDIAN] = 0x00;
         }
     }
+    if (trans < 0)
+        honor_transparency = 0;
 
     bytestream_put_byte(bytestream, 0x08);
 
@@ -172,7 +178,7 @@ static int gif_image_write_image(AVCodecContext *avctx,
                        12, FF_LZW_GIF, put_bits);
 
     ptr = buf + y_start*linesize + x_start;
-    if (trans >= 0) {
+    if (honor_transparency) {
         const int ref_linesize = s->last_frame->linesize[0];
         const uint8_t *ref = s->last_frame->data[0] + y_start*ref_linesize + x_start;
 
@@ -223,6 +229,8 @@ static av_cold int gif_encode_init(AVCodecContext *avctx)
     avctx->coded_frame->pict_type = AV_PICTURE_TYPE_I;
     avctx->coded_frame->key_frame = 1;
 
+    s->transparent_index = -1;
+
     s->lzw = av_mallocz(ff_lzw_encode_state_size);
     s->buf = av_malloc(avctx->width*avctx->height*2);
     s->tmpl = av_malloc(avctx->width);
@@ -235,6 +243,25 @@ static av_cold int gif_encode_init(AVCodecContext *avctx)
     return 0;
 }
 
+/* FIXME: duplicated with lavc */
+static int get_palette_transparency_index(const uint32_t *palette)
+{
+    int transparent_color_index = -1;
+    unsigned i, smallest_alpha = 0xff;
+
+    if (!palette)
+        return -1;
+
+    for (i = 0; i < AVPALETTE_COUNT; i++) {
+        const uint32_t v = palette[i];
+        if (v >> 24 < smallest_alpha) {
+            smallest_alpha = v >> 24;
+            transparent_color_index = i;
+        }
+    }
+    return smallest_alpha < 128 ? transparent_color_index : -1;
+}
+
 static int gif_encode_frame(AVCodecContext *avctx, AVPacket *pkt,
                             const AVFrame *pict, int *got_packet)
 {
@@ -254,6 +281,20 @@ static int gif_encode_frame(AVCodecContext *avctx, AVPacket *pkt,
             return AVERROR(ENOMEM);
         memcpy(pal_exdata, pict->data[1], AVPALETTE_SIZE);
         palette = (uint32_t*)pict->data[1];
+
+        s->pal_exdata = pal_exdata;
+
+        /* The first palette with PAL8 will be used as generic palette by the
+         * muxer so we don't need to write it locally in the packet. We store
+         * it as a reference here in case it changes later. */
+        if (!s->palette_loaded) {
+            memcpy(s->palette, palette, AVPALETTE_SIZE);
+            s->transparent_index = get_palette_transparency_index(palette);
+            s->palette_loaded = 1;
+            palette = NULL;
+        } else if (!memcmp(s->palette, palette, AVPALETTE_SIZE)) {
+            palette = NULL;
+        }
     }
 
     gif_image_write_image(avctx, &outbuf_ptr, end, palette,
index 203a154..ede614c 100644 (file)
 #tb 0: 1/10
-0,          0,          0,        1,     1320, 0x95d1a9e9, S=1,     1024, 0xec907a9e
-0,          1,          1,        1,     1463, 0xa697fe95, S=1,     1024, 0xec907a9e
-0,          2,          2,        1,     1638, 0x7ea154fa, S=1,     1024, 0xec907a9e
-0,          3,          3,        1,     1755, 0x7e0b9c4d, S=1,     1024, 0xec907a9e
-0,          4,          4,        1,     1896, 0x4aacc768, S=1,     1024, 0xec907a9e
-0,          5,          5,        1,     2038, 0x209d1490, S=1,     1024, 0xec907a9e
-0,          6,          6,        1,     2168, 0x0c405606, S=1,     1024, 0xec907a9e
-0,          7,          7,        1,     2258, 0xc2fa9229, S=1,     1024, 0xec907a9e
-0,          8,          8,        1,     2442, 0x0d4bec48, S=1,     1024, 0xec907a9e
-0,          9,          9,        1,     2565, 0x15742730, S=1,     1024, 0xec907a9e
-0,         10,         10,        1,     2733, 0x2eb57d95, S=1,     1024, 0xec907a9e
-0,         11,         11,        1,     2849, 0x9f16ad46, S=1,     1024, 0xec907a9e
-0,         12,         12,        1,     2981, 0xf139f908, S=1,     1024, 0xec907a9e
-0,         13,         13,        1,     3082, 0x57144aec, S=1,     1024, 0xec907a9e
-0,         14,         14,        1,     3200, 0x35227f42, S=1,     1024, 0xec907a9e
-0,         15,         15,        1,     3316, 0xf6d7c002, S=1,     1024, 0xec907a9e
-0,         16,         16,        1,     3462, 0x27a20d23, S=1,     1024, 0xec907a9e
-0,         17,         17,        1,     3600, 0xaecb2b02, S=1,     1024, 0xec907a9e
-0,         18,         18,        1,     3712, 0x947d49d1, S=1,     1024, 0xec907a9e
-0,         19,         19,        1,     3838, 0xf87eb223, S=1,     1024, 0xec907a9e
-0,         20,         20,        1,     3949, 0x4152eedf, S=1,     1024, 0xec907a9e
-0,         21,         21,        1,     4084, 0x512c1e34, S=1,     1024, 0xec907a9e
-0,         22,         22,        1,     4187, 0xc5715a14, S=1,     1024, 0xec907a9e
-0,         23,         23,        1,     4323, 0x6326a0f5, S=1,     1024, 0xec907a9e
-0,         24,         24,        1,     4426, 0x5f6bd655, S=1,     1024, 0xec907a9e
-0,         25,         25,        1,     4564, 0xc62005fd, S=1,     1024, 0xec907a9e
-0,         26,         26,        1,     4664, 0x43e97006, S=1,     1024, 0xec907a9e
-0,         27,         27,        1,     4808, 0xf6e08d4f, S=1,     1024, 0xec907a9e
-0,         28,         28,        1,     4932, 0x2d51e0b5, S=1,     1024, 0xec907a9e
-0,         29,         29,        1,     5072, 0x577430c8, S=1,     1024, 0xec907a9e
-0,         30,         30,        1,     5247, 0xd9fe945d, S=1,     1024, 0xec907a9e
-0,         31,         31,        1,     5353, 0x27eec140, S=1,     1024, 0xec907a9e
-0,         32,         32,        1,     5536, 0xde59038d, S=1,     1024, 0xec907a9e
-0,         33,         33,        1,     5691, 0x358970e4, S=1,     1024, 0xec907a9e
-0,         34,         34,        1,     5835, 0xd89201d8, S=1,     1024, 0xec907a9e
-0,         35,         35,        1,     5967, 0x1c2e1fee, S=1,     1024, 0xec907a9e
-0,         36,         36,        1,     6082, 0xd4b88e90, S=1,     1024, 0xec907a9e
-0,         37,         37,        1,     6277, 0x020fe685, S=1,     1024, 0xec907a9e
-0,         38,         38,        1,     6382, 0xc1db2297, S=1,     1024, 0xec907a9e
-0,         39,         39,        1,     6509, 0xc65473a6, S=1,     1024, 0xec907a9e
-0,         40,         40,        1,     6621, 0xca917a35, S=1,     1024, 0xec907a9e
-0,         41,         41,        1,     6714, 0x70f29b1d, S=1,     1024, 0xec907a9e
-0,         42,         42,        1,     6822, 0x6f02e7ec, S=1,     1024, 0xec907a9e
-0,         43,         43,        1,     6880, 0x95440d97, S=1,     1024, 0xec907a9e
-0,         44,         44,        1,     6983, 0xab7a43fb, S=1,     1024, 0xec907a9e
-0,         45,         45,        1,     7085, 0xc3427580, S=1,     1024, 0xec907a9e
-0,         46,         46,        1,     7242, 0x3d00c5f0, S=1,     1024, 0xec907a9e
-0,         47,         47,        1,     7349, 0x453fad59, S=1,     1024, 0xec907a9e
-0,         48,         48,        1,     7514, 0xbd862667, S=1,     1024, 0xec907a9e
-0,         49,         49,        1,     7575, 0xf8cb3c77, S=1,     1024, 0xec907a9e
-0,         50,         50,        1,     7759, 0x1fe6ab40, S=1,     1024, 0xec907a9e
-0,         51,         51,        1,     7846, 0x3853fd0f, S=1,     1024, 0xec907a9e
-0,         52,         52,        1,     7975, 0x88d02c47, S=1,     1024, 0xec907a9e
-0,         53,         53,        1,     8092, 0xe28a3368, S=1,     1024, 0xec907a9e
-0,         54,         54,        1,     8188, 0x159a5d3b, S=1,     1024, 0xec907a9e
-0,         55,         55,        1,     8307, 0x598cae50, S=1,     1024, 0xec907a9e
-0,         56,         56,        1,     8436, 0xd104ee50, S=1,     1024, 0xec907a9e
-0,         57,         57,        1,     8498, 0x0b1527ed, S=1,     1024, 0xec907a9e
-0,         58,         58,        1,     8559, 0x0f722288, S=1,     1024, 0xec907a9e
-0,         59,         59,        1,     8661, 0x3efb2500, S=1,     1024, 0xec907a9e
-0,         60,         60,        1,     8774, 0x1e188a8b, S=1,     1024, 0xec907a9e
-0,         61,         61,        1,     8848, 0x5b438dbb, S=1,     1024, 0xec907a9e
-0,         62,         62,        1,     8968, 0x4b47ecb3, S=1,     1024, 0xec907a9e
-0,         63,         63,        1,     9036, 0x7a8e0791, S=1,     1024, 0xec907a9e
-0,         64,         64,        1,     9114, 0x7379131a, S=1,     1024, 0xec907a9e
-0,         65,         65,        1,     9258, 0x06099246, S=1,     1024, 0xec907a9e
-0,         66,         66,        1,     9423, 0x721ac9ab, S=1,     1024, 0xec907a9e
-0,         67,         67,        1,     9529, 0xbb1c0d18, S=1,     1024, 0xec907a9e
-0,         68,         68,        1,     9608, 0xc29a05f0, S=1,     1024, 0xec907a9e
-0,         69,         69,        1,     9668, 0xf35221ff, S=1,     1024, 0xec907a9e
-0,         70,         70,        1,     9709, 0x8c6d33f0, S=1,     1024, 0xec907a9e
-0,         71,         71,        1,     9810, 0x2d5b59f4, S=1,     1024, 0xec907a9e
-0,         72,         72,        1,     9879, 0x110ea6e5, S=1,     1024, 0xec907a9e
-0,         73,         73,        1,    10038, 0x5945f5f4, S=1,     1024, 0xec907a9e
-0,         74,         74,        1,    10120, 0xab24f519, S=1,     1024, 0xec907a9e
-0,         75,         75,        1,    10218, 0x090d305a, S=1,     1024, 0xec907a9e
-0,         76,         76,        1,    10231, 0xa77e6a66, S=1,     1024, 0xec907a9e
-0,         77,         77,        1,    10313, 0x192254b7, S=1,     1024, 0xec907a9e
-0,         78,         78,        1,    10444, 0x36609934, S=1,     1024, 0xec907a9e
-0,         79,         79,        1,    10670, 0xfa971206, S=1,     1024, 0xec907a9e
-0,         80,         80,        1,    10902, 0x01b59fd5, S=1,     1024, 0xec907a9e
-0,         81,         81,        1,    10992, 0x1f2ab0bc, S=1,     1024, 0xec907a9e
-0,         82,         82,        1,    11044, 0x7f5b1dc2, S=1,     1024, 0xec907a9e
-0,         83,         83,        1,    11170, 0x0beaee49, S=1,     1024, 0xec907a9e
-0,         84,         84,        1,    11267, 0xb1ae3808, S=1,     1024, 0xec907a9e
-0,         85,         85,        1,    11427, 0x2cc9aa3f, S=1,     1024, 0xec907a9e
-0,         86,         86,        1,    11529, 0x654de4f3, S=1,     1024, 0xec907a9e
-0,         87,         87,        1,    11632, 0xf4972bdf, S=1,     1024, 0xec907a9e
-0,         88,         88,        1,    11825, 0x0cd2548c, S=1,     1024, 0xec907a9e
-0,         89,         89,        1,    11864, 0x80758637, S=1,     1024, 0xec907a9e
-0,         90,         90,        1,    11950, 0xf8246fba, S=1,     1024, 0xec907a9e
-0,         91,         91,        1,    12088, 0x1b99c82b, S=1,     1024, 0xec907a9e
-0,         92,         92,        1,    12161, 0x682cf4ad, S=1,     1024, 0xec907a9e
-0,         93,         93,        1,    12305, 0x9f62069a, S=1,     1024, 0xec907a9e
-0,         94,         94,        1,    12296, 0xe08dd96c, S=1,     1024, 0xec907a9e
-0,         95,         95,        1,    12497, 0x9a20b2d0, S=1,     1024, 0xec907a9e
-0,         96,         96,        1,    12660, 0x4d1d05ea, S=1,     1024, 0xec907a9e
-0,         97,         97,        1,    12763, 0x12542531, S=1,     1024, 0xec907a9e
-0,         98,         98,        1,    12917, 0x7d0944dc, S=1,     1024, 0xec907a9e
-0,         99,         99,        1,    13021, 0xa1c89f22, S=1,     1024, 0xec907a9e
-0,        100,        100,        1,    13184, 0xe13ad0be, S=1,     1024, 0xec907a9e
-0,        101,        101,        1,    13315, 0x11b93a5d, S=1,     1024, 0xec907a9e
-0,        102,        102,        1,    13337, 0x677e54ef, S=1,     1024, 0xec907a9e
-0,        103,        103,        1,    13536, 0x48b7b5de, S=1,     1024, 0xec907a9e
-0,        104,        104,        1,    13728, 0x03f4d302, S=1,     1024, 0xec907a9e
-0,        105,        105,        1,    13822, 0x973b97ec, S=1,     1024, 0xec907a9e
-0,        106,        106,        1,    14002, 0x0de77dfc, S=1,     1024, 0xec907a9e
-0,        107,        107,        1,    14156, 0xf1b1d4e1, S=1,     1024, 0xec907a9e
-0,        108,        108,        1,    14256, 0x355320cc, S=1,     1024, 0xec907a9e
-0,        109,        109,        1,    14451, 0x306cb131, S=1,     1024, 0xec907a9e
-0,        110,        110,        1,    14508, 0xca729c8e, S=1,     1024, 0xec907a9e
-0,        111,        111,        1,    14683, 0x7abec197, S=1,     1024, 0xec907a9e
-0,        112,        112,        1,    14852, 0xa5b90496, S=1,     1024, 0xec907a9e
-0,        113,        113,        1,    15090, 0xcd29839d, S=1,     1024, 0xec907a9e
-0,        114,        114,        1,    15225, 0xfd85f899, S=1,     1024, 0xec907a9e
-0,        115,        115,        1,    15340, 0x07411310, S=1,     1024, 0xec907a9e
-0,        116,        116,        1,    15473, 0xe90086c1, S=1,     1024, 0xec907a9e
-0,        117,        117,        1,    15583, 0x524da1f3, S=1,     1024, 0xec907a9e
-0,        118,        118,        1,    15683, 0x404cbd62, S=1,     1024, 0xec907a9e
-0,        119,        119,        1,    15779, 0x3ec01717, S=1,     1024, 0xec907a9e
-0,        120,        120,        1,    15934, 0xac8b4c03, S=1,     1024, 0xec907a9e
-0,        121,        121,        1,    16116, 0xb4fa83c9, S=1,     1024, 0xec907a9e
-0,        122,        122,        1,    16153, 0x18f669c1, S=1,     1024, 0xec907a9e
-0,        123,        123,        1,    16303, 0x765b10e4, S=1,     1024, 0xec907a9e
-0,        124,        124,        1,    16460, 0xc4a8149a, S=1,     1024, 0xec907a9e
-0,        125,        125,        1,    16475, 0x48664e2d, S=1,     1024, 0xec907a9e
-0,        126,        126,        1,    16710, 0x8a599742, S=1,     1024, 0xec907a9e
-0,        127,        127,        1,    16848, 0x8634a3d5, S=1,     1024, 0xec907a9e
-0,        128,        128,        1,    16955, 0x01f1ebda, S=1,     1024, 0xec907a9e
-0,        129,        129,        1,    17044, 0xd57b47df, S=1,     1024, 0xec907a9e
-0,        130,        130,        1,    17153, 0xc5cf7bc7, S=1,     1024, 0xec907a9e
-0,        131,        131,        1,    17375, 0xbbeea767, S=1,     1024, 0xec907a9e
-0,        132,        132,        1,    17476, 0xd7a25686, S=1,     1024, 0xec907a9e
-0,        133,        133,        1,    17602, 0x1c99b228, S=1,     1024, 0xec907a9e
-0,        134,        134,        1,    17676, 0xd860d1d2, S=1,     1024, 0xec907a9e
-0,        135,        135,        1,    17799, 0xe4ccb3ae, S=1,     1024, 0xec907a9e
-0,        136,        136,        1,    17930, 0xf322e416, S=1,     1024, 0xec907a9e
-0,        137,        137,        1,    18201, 0xc6f1cfa7, S=1,     1024, 0xec907a9e
-0,        138,        138,        1,    18409, 0x7cdfe609, S=1,     1024, 0xec907a9e
-0,        139,        139,        1,    18686, 0xf65e5519, S=1,     1024, 0xec907a9e
-0,        140,        140,        1,    18790, 0x6d5c8a90, S=1,     1024, 0xec907a9e
-0,        141,        141,        1,    18891, 0x4702a6cf, S=1,     1024, 0xec907a9e
-0,        142,        142,        1,    18995, 0x69e5e02d, S=1,     1024, 0xec907a9e
-0,        143,        143,        1,    19058, 0xc56f0272, S=1,     1024, 0xec907a9e
-0,        144,        144,        1,    19223, 0xe89733f6, S=1,     1024, 0xec907a9e
-0,        145,        145,        1,    19501, 0xdb80f9e9, S=1,     1024, 0xec907a9e
-0,        146,        146,        1,    19566, 0xa3952da8, S=1,     1024, 0xec907a9e
-0,        147,        147,        1,    19692, 0x65925150, S=1,     1024, 0xec907a9e
-0,        148,        148,        1,    19730, 0x1352599a, S=1,     1024, 0xec907a9e
-0,        149,        149,        1,    19916, 0xd246bf9b, S=1,     1024, 0xec907a9e
-0,        150,        150,        1,    20136, 0x1c462eea, S=1,     1024, 0xec907a9e
-0,        151,        151,        1,    20210, 0xdec93f63, S=1,     1024, 0xec907a9e
-0,        152,        152,        1,    20311, 0xdff7836e, S=1,     1024, 0xec907a9e
-0,        153,        153,        1,    20377, 0x753d813f, S=1,     1024, 0xec907a9e
-0,        154,        154,        1,    20478, 0x7592b1a8, S=1,     1024, 0xec907a9e
-0,        155,        155,        1,    20597, 0x58313994, S=1,     1024, 0xec907a9e
-0,        156,        156,        1,    20717, 0xcdd9c665, S=1,     1024, 0xec907a9e
-0,        157,        157,        1,    20816, 0x803b4b03, S=1,     1024, 0xec907a9e
-0,        158,        158,        1,    20912, 0xce36ce22, S=1,     1024, 0xec907a9e
-0,        159,        159,        1,    20975, 0x1d08e543, S=1,     1024, 0xec907a9e
-0,        160,        160,        1,    21130, 0xc966e24c, S=1,     1024, 0xec907a9e
-0,        161,        161,        1,    21343, 0x735e614e, S=1,     1024, 0xec907a9e
-0,        162,        162,        1,    21455, 0x78d7afd1, S=1,     1024, 0xec907a9e
-0,        163,        163,        1,    21533, 0x62a10f46, S=1,     1024, 0xec907a9e
-0,        164,        164,        1,    21645, 0x8e53a12f, S=1,     1024, 0xec907a9e
-0,        165,        165,        1,    21931, 0x3b2f7226, S=1,     1024, 0xec907a9e
-0,        166,        166,        1,    22009, 0xf06bc58a, S=1,     1024, 0xec907a9e
-0,        167,        167,        1,    22115, 0xeeb1c5d7, S=1,     1024, 0xec907a9e
-0,        168,        168,        1,    22211, 0xcbab1084, S=1,     1024, 0xec907a9e
-0,        169,        169,        1,    22380, 0xf07d5cb7, S=1,     1024, 0xec907a9e
-0,        170,        170,        1,    22443, 0xcb79441c, S=1,     1024, 0xec907a9e
-0,        171,        171,        1,    22588, 0xcad49814, S=1,     1024, 0xec907a9e
-0,        172,        172,        1,    22706, 0x34924e43, S=1,     1024, 0xec907a9e
+0,          0,          0,        1,      552, 0x271a2dd3, S=1,     1024, 0xec907a9e
+0,          1,          1,        1,      297, 0x90168a95, S=1,     1024, 0xf351799f
+0,          2,          2,        1,      438, 0x91efce1b, S=1,     1024, 0xf351799f
+0,          3,          3,        1,      450, 0x7c2dcfad, S=1,     1024, 0xf351799f
+0,          4,          4,        1,      547, 0xc131fd3b, S=1,     1024, 0xf351799f
+0,          5,          5,        1,      614, 0x68182006, S=1,     1024, 0xf351799f
+0,          6,          6,        1,      642, 0x78bb1f5f, S=1,     1024, 0xf351799f
+0,          7,          7,        1,      660, 0x35c033a2, S=1,     1024, 0xf351799f
+0,          8,          8,        1,      821, 0xaf30790b, S=1,     1024, 0xf351799f
+0,          9,          9,        1,     1157, 0x741c2da1, S=1,     1024, 0xf351799f
+0,         10,         10,        1,      179, 0x3a27517c, S=1,     1024, 0xf351799f
+0,         11,         11,        1,     1333, 0x5ee76f3c, S=1,     1024, 0xf351799f
+0,         12,         12,        1,     1638, 0x5f640e86, S=1,     1024, 0xf351799f
+0,         13,         13,        1,     1531, 0xccb8e437, S=1,     1024, 0xf351799f
+0,         14,         14,        1,     1720, 0xc95d45ec, S=1,     1024, 0xf351799f
+0,         15,         15,        1,     1910, 0x56cc831e, S=1,     1024, 0xf351799f
+0,         16,         16,        1,     2124, 0x9cc8e130, S=1,     1024, 0xf351799f
+0,         17,         17,        1,     2248, 0x05a325b1, S=1,     1024, 0xf351799f
+0,         18,         18,        1,     2311, 0xdc633703, S=1,     1024, 0xf351799f
+0,         19,         19,        1,     2408, 0x91c26f3e, S=1,     1024, 0xf351799f
+0,         20,         20,        1,     2601, 0x8cf3c157, S=1,     1024, 0xf351799f
+0,         21,         21,        1,     2687, 0x8f6400e6, S=1,     1024, 0xf351799f
+0,         22,         22,        1,     2784, 0xaa880e55, S=1,     1024, 0xf351799f
+0,         23,         23,        1,     2884, 0x46f546f6, S=1,     1024, 0xf351799f
+0,         24,         24,        1,     2982, 0x807c7ad5, S=1,     1024, 0xf351799f
+0,         25,         25,        1,     3101, 0xbcc89bec, S=1,     1024, 0xf351799f
+0,         26,         26,        1,     3253, 0xd032f3fa, S=1,     1024, 0xf351799f
+0,         27,         27,        1,     3329, 0xe4d42430, S=1,     1024, 0xf351799f
+0,         28,         28,        1,     3572, 0xf8058aa0, S=1,     1024, 0xf351799f
+0,         29,         29,        1,     3807, 0x3d2af9f3, S=1,     1024, 0xf351799f
+0,         30,         30,        1,     2750, 0x814d1c33, S=1,     1024, 0xf351799f
+0,         31,         31,        1,     4031, 0x3b077006, S=1,     1024, 0xf351799f
+0,         32,         32,        1,     3025, 0x86729c1c, S=1,     1024, 0xf351799f
+0,         33,         33,        1,     4295, 0xf71b0b38, S=1,     1024, 0xf351799f
+0,         34,         34,        1,     2044, 0x5adcb93b, S=1,     1024, 0xf351799f
+0,         35,         35,        1,     3212, 0xcf79eeed, S=1,     1024, 0xf351799f
+0,         36,         36,        1,     2281, 0x68464d30, S=1,     1024, 0xf351799f
+0,         37,         37,        1,     3633, 0x0010992f, S=1,     1024, 0xf351799f
+0,         38,         38,        1,     3552, 0x23697490, S=1,     1024, 0xf351799f
+0,         39,         39,        1,     3690, 0x62afdbb8, S=1,     1024, 0xf351799f
+0,         40,         40,        1,     1558, 0x7a13e53b, S=1,     1024, 0xf351799f
+0,         41,         41,        1,      940, 0xb1b6cba2, S=1,     1024, 0xf351799f
+0,         42,         42,        1,      273, 0x3687799b, S=1,     1024, 0xf351799f
+0,         43,         43,        1,      930, 0x29f3b0c4, S=1,     1024, 0xf351799f
+0,         44,         44,        1,      271, 0xe7af807c, S=1,     1024, 0xf351799f
+0,         45,         45,        1,      196, 0xf5ab51ee, S=1,     1024, 0xf351799f
+0,         46,         46,        1,     4299, 0x67ec0d55, S=1,     1024, 0xf351799f
+0,         47,         47,        1,     4895, 0xb394406c, S=1,     1024, 0xf351799f
+0,         48,         48,        1,     4928, 0x233919d7, S=1,     1024, 0xf351799f
+0,         49,         49,        1,     4941, 0x58a357da, S=1,     1024, 0xf351799f
+0,         50,         50,        1,     4154, 0x21f2ac33, S=1,     1024, 0xf351799f
+0,         51,         51,        1,     4678, 0xab3cc050, S=1,     1024, 0xf351799f
+0,         52,         52,        1,     4741, 0x1974b581, S=1,     1024, 0xf351799f
+0,         53,         53,        1,     4982, 0x891456d5, S=1,     1024, 0xf351799f
+0,         54,         54,        1,     5179, 0x860fc6a1, S=1,     1024, 0xf351799f
+0,         55,         55,        1,     5046, 0xce9183d3, S=1,     1024, 0xf351799f
+0,         56,         56,        1,     5140, 0xa6d7b9af, S=1,     1024, 0xf351799f
+0,         57,         57,        1,     4289, 0xb415f717, S=1,     1024, 0xf351799f
+0,         58,         58,        1,     5079, 0xa8d59e01, S=1,     1024, 0xf351799f
+0,         59,         59,        1,     5284, 0xea34e3b3, S=1,     1024, 0xf351799f
+0,         60,         60,        1,     5426, 0x556a15cd, S=1,     1024, 0xf351799f
+0,         61,         61,        1,     4645, 0x061e8936, S=1,     1024, 0xf351799f
+0,         62,         62,        1,     5263, 0x7536cf7d, S=1,     1024, 0xf351799f
+0,         63,         63,        1,     5221, 0x9fbac3ca, S=1,     1024, 0xf351799f
+0,         64,         64,        1,     5217, 0x02269bd2, S=1,     1024, 0xf351799f
+0,         65,         65,        1,     5395, 0x120fff66, S=1,     1024, 0xf351799f
+0,         66,         66,        1,     5220, 0x77cedcc5, S=1,     1024, 0xf351799f
+0,         67,         67,        1,     5704, 0xba42dd96, S=1,     1024, 0xf351799f
+0,         68,         68,        1,     5636, 0xcb91a25b, S=1,     1024, 0xf351799f
+0,         69,         69,        1,     5818, 0x8dc0df92, S=1,     1024, 0xf351799f
+0,         70,         70,        1,     5763, 0x51d5d5f0, S=1,     1024, 0xf351799f
+0,         71,         71,        1,     6116, 0x09558b48, S=1,     1024, 0xf351799f
+0,         72,         72,        1,     6069, 0x41926817, S=1,     1024, 0xf351799f
+0,         73,         73,        1,     5796, 0x7fbeda44, S=1,     1024, 0xf351799f
+0,         74,         74,        1,     5999, 0xe07d3770, S=1,     1024, 0xf351799f
+0,         75,         75,        1,     6220, 0x6607b06f, S=1,     1024, 0xf351799f
+0,         76,         76,        1,     6374, 0x7628e533, S=1,     1024, 0xf351799f
+0,         77,         77,        1,     6465, 0xfe956b15, S=1,     1024, 0xf351799f
+0,         78,         78,        1,     7019, 0x6c9a1aef, S=1,     1024, 0xf351799f
+0,         79,         79,        1,     7255, 0x5fa5c1bf, S=1,     1024, 0xf351799f
+0,         80,         80,        1,     8197, 0xf11d6ef2, S=1,     1024, 0xf351799f
+0,         81,         81,        1,     8358, 0x027279e8, S=1,     1024, 0xf351799f
+0,         82,         82,        1,     7708, 0x607f8e8b, S=1,     1024, 0xf351799f
+0,         83,         83,        1,     7412, 0x6bb2105f, S=1,     1024, 0xf351799f
+0,         84,         84,        1,     7541, 0xfdc02154, S=1,     1024, 0xf351799f
+0,         85,         85,        1,     7948, 0x916ecd8b, S=1,     1024, 0xf351799f
+0,         86,         86,        1,     8408, 0x1f97d414, S=1,     1024, 0xf351799f
+0,         87,         87,        1,     8056, 0x9cbf159c, S=1,     1024, 0xf351799f
+0,         88,         88,        1,     7401, 0x2625addb, S=1,     1024, 0xf351799f
+0,         89,         89,        1,     7494, 0x2877eacb, S=1,     1024, 0xf351799f
+0,         90,         90,        1,     7806, 0xe32574a3, S=1,     1024, 0xf351799f
+0,         91,         91,        1,     7768, 0x25ed7ee7, S=1,     1024, 0xf351799f
+0,         92,         92,        1,     7749, 0x6d8e978e, S=1,     1024, 0xf351799f
+0,         93,         93,        1,     8047, 0xec4b150c, S=1,     1024, 0xf351799f
+0,         94,         94,        1,     7618, 0x88cf30d5, S=1,     1024, 0xf351799f
+0,         95,         95,        1,     7979, 0x0eb1cf2a, S=1,     1024, 0xf351799f
+0,         96,         96,        1,    12062, 0xb49d9125, S=1,     1024, 0xf351799f
+0,         97,         97,        1,    12317, 0x2d8fd6e9, S=1,     1024, 0xf351799f
+0,         98,         98,        1,    12217, 0x9b3be549, S=1,     1024, 0xf351799f
+0,         99,         99,        1,    11227, 0x067e9118, S=1,     1024, 0xf351799f
+0,        100,        100,        1,    11108, 0x5e5b0afd, S=1,     1024, 0xf351799f
+0,        101,        101,        1,    11366, 0xb38e8d15, S=1,     1024, 0xf351799f
+0,        102,        102,        1,    11896, 0xeb3e35ca, S=1,     1024, 0xf351799f
+0,        103,        103,        1,    11479, 0xbf7581e9, S=1,     1024, 0xf351799f
+0,        104,        104,        1,    13395, 0x415b38d8, S=1,     1024, 0xf351799f
+0,        105,        105,        1,    12913, 0x61544631, S=1,     1024, 0xf351799f
+0,        106,        106,        1,    13864, 0xd39fe768, S=1,     1024, 0xf351799f
+0,        107,        107,        1,    13551, 0x76c167d1, S=1,     1024, 0xf351799f
+0,        108,        108,        1,    14041, 0x2f206888, S=1,     1024, 0xf351799f
+0,        109,        109,        1,    14144, 0x9ec030d3, S=1,     1024, 0xf351799f
+0,        110,        110,        1,    14277, 0xa84b3a9b, S=1,     1024, 0xf351799f
+0,        111,        111,        1,    14424, 0xf5f1e06e, S=1,     1024, 0xf351799f
+0,        112,        112,        1,    14689, 0xbca0adb5, S=1,     1024, 0xf351799f
+0,        113,        113,        1,    14598, 0xc1d45745, S=1,     1024, 0xf351799f
+0,        114,        114,        1,    15213, 0x8f3080fc, S=1,     1024, 0xf351799f
+0,        115,        115,        1,    15425, 0xb0aa8f59, S=1,     1024, 0xf351799f
+0,        116,        116,        1,    15595, 0x1406e5d5, S=1,     1024, 0xf351799f
+0,        117,        117,        1,    15598, 0x48ec7d08, S=1,     1024, 0xf351799f
+0,        118,        118,        1,    15863, 0x5381db7b, S=1,     1024, 0xf351799f
+0,        119,        119,        1,    15717, 0xb87a1b87, S=1,     1024, 0xf351799f
+0,        120,        120,        1,    16078, 0x5bab2453, S=1,     1024, 0xf351799f
+0,        121,        121,        1,    16225, 0xa1f88113, S=1,     1024, 0xf351799f
+0,        122,        122,        1,    16135, 0x6af2f4e1, S=1,     1024, 0xf351799f
+0,        123,        123,        1,    16661, 0xf02a3343, S=1,     1024, 0xf351799f
+0,        124,        124,        1,    16619, 0xc71935a4, S=1,     1024, 0xf351799f
+0,        125,        125,        1,    16829, 0x29849844, S=1,     1024, 0xf351799f
+0,        126,        126,        1,    16944, 0x3423ae77, S=1,     1024, 0xf351799f
+0,        127,        127,        1,    17119, 0x609b4409, S=1,     1024, 0xf351799f
+0,        128,        128,        1,    17150, 0xf85dfd31, S=1,     1024, 0xf351799f
+0,        129,        129,        1,    17321, 0x38eccb10, S=1,     1024, 0xf351799f
+0,        130,        130,        1,    17395, 0x0ba08b85, S=1,     1024, 0xf351799f
+0,        131,        131,        1,    17666, 0x6fbc0264, S=1,     1024, 0xf351799f
+0,        132,        132,        1,    17730, 0x3dcc64a6, S=1,     1024, 0xf351799f
+0,        133,        133,        1,    17934, 0xb539974b, S=1,     1024, 0xf351799f
+0,        134,        134,        1,    17944, 0x2214ec94, S=1,     1024, 0xf351799f
+0,        135,        135,        1,    18238, 0x70f9ff1d, S=1,     1024, 0xf351799f
+0,        136,        136,        1,    18391, 0x4b149209, S=1,     1024, 0xf351799f
+0,        137,        137,        1,    18543, 0x45a1c02f, S=1,     1024, 0xf351799f
+0,        138,        138,        1,    18939, 0x2789a88c, S=1,     1024, 0xf351799f
+0,        139,        139,        1,    19145, 0x5daafd7a, S=1,     1024, 0xf351799f
+0,        140,        140,        1,    19120, 0x565f80e6, S=1,     1024, 0xf351799f
+0,        141,        141,        1,    19130, 0xff70cc21, S=1,     1024, 0xf351799f
+0,        142,        142,        1,    19494, 0xbfa284db, S=1,     1024, 0xf351799f
+0,        143,        143,        1,    19534, 0x3d40743b, S=1,     1024, 0xf351799f
+0,        144,        144,        1,    19747, 0x33c9b108, S=1,     1024, 0xf351799f
+0,        145,        145,        1,    20114, 0x9d223e36, S=1,     1024, 0xf351799f
+0,        146,        146,        1,    20257, 0xe7bdaf43, S=1,     1024, 0xf351799f
+0,        147,        147,        1,    20370, 0x0c5f1970, S=1,     1024, 0xf351799f
+0,        148,        148,        1,    20292, 0x6986d20e, S=1,     1024, 0xf351799f
+0,        149,        149,        1,    20491, 0xd88e4c08, S=1,     1024, 0xf351799f
+0,        150,        150,        1,    20647, 0x1aefaffc, S=1,     1024, 0xf351799f
+0,        151,        151,        1,    20666, 0x43e4aaaa, S=1,     1024, 0xf351799f
+0,        152,        152,        1,    21007, 0xa7ca3ef0, S=1,     1024, 0xf351799f
+0,        153,        153,        1,    21058, 0x06814351, S=1,     1024, 0xf351799f
+0,        154,        154,        1,    21153, 0x3c852b10, S=1,     1024, 0xf351799f
+0,        155,        155,        1,    21078, 0x8df15855, S=1,     1024, 0xf351799f
+0,        156,        156,        1,    21458, 0xd3a531d6, S=1,     1024, 0xf351799f
+0,        157,        157,        1,    21669, 0x88baca53, S=1,     1024, 0xf351799f
+0,        158,        158,        1,    21581, 0xd692fa1f, S=1,     1024, 0xf351799f
+0,        159,        159,        1,    21654, 0x30fb9061, S=1,     1024, 0xf351799f
+0,        160,        160,        1,    21987, 0xe7646d8b, S=1,     1024, 0xf351799f
+0,        161,        161,        1,    22205, 0x0fc55b6a, S=1,     1024, 0xf351799f
+0,        162,        162,        1,    22475, 0x4bc4c032, S=1,     1024, 0xf351799f
+0,        163,        163,        1,    22490, 0x58ca23f6, S=1,     1024, 0xf351799f
+0,        164,        164,        1,    22460, 0xf9ceb0ac, S=1,     1024, 0xf351799f
+0,        165,        165,        1,    22861, 0xb05f0f84, S=1,     1024, 0xf351799f
+0,        166,        166,        1,    22746, 0x0df23a5c, S=1,     1024, 0xf351799f
+0,        167,        167,        1,    23165, 0xbd7147ad, S=1,     1024, 0xf351799f
+0,        168,        168,        1,    23273, 0x9781a34f, S=1,     1024, 0xf351799f
+0,        169,        169,        1,    23211, 0x69c7606b, S=1,     1024, 0xf351799f
+0,        170,        170,        1,    23648, 0xdafde037, S=1,     1024, 0xf351799f
+0,        171,        171,        1,    23675, 0x2a2147ed, S=1,     1024, 0xf351799f
+0,        172,        172,        1,    23874, 0x12c184b6, S=1,     1024, 0xf351799f