"Fossies" - the Fresh Open Source Software Archive

Member "haproxy-2.0.9/contrib/hpack/gen-rht.c" (15 Nov 2019, 13196 Bytes) of package /linux/misc/haproxy-2.0.9.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "gen-rht.c" see the Fossies "Dox" file reference documentation.

    1 /* Reverse Huffman table generator for HPACK decoder - 2017-05-19 Willy Tarreau
    2  *
    3  * rht_bit31_24[256]   is indexed on bits 31..24 when < 0xfe
    4  * rht_bit24_17[256]   is indexed on bits 24..17 when 31..24 >= 0xfe
    5  * rht_bit15_11_fe[32] is indexed on bits 15..11 when 24..17 == 0xfe
    6  * rht_bit15_8[256]    is indexed on bits 15..8 when 24..17 == 0xff
    7  * rht_bit11_4[256]    is indexed on bits 11..4 when 15..8 == 0xff
    8  * when 11..4 == 0xff, 3..2 provide the following mapping :
    9  *   00 => 0x0a, 01 => 0x0d, 10 => 0x16, 11 => EOS
   10  */
   11 
   12 #include <inttypes.h>
   13 #include <stdio.h>
   14 #include <stdlib.h>
   15 #include <string.h>
   16 
   17 /* from RFC7541 Appendix B */
   18 static const struct huff {
   19     uint32_t c; /* code point */
   20     int b;      /* bits */
   21 } ht[257] = {
   22     [0] = { .c = 0x00001ff8, .b = 13 },
   23     [1] = { .c = 0x007fffd8, .b = 23 },
   24     [2] = { .c = 0x0fffffe2, .b = 28 },
   25     [3] = { .c = 0x0fffffe3, .b = 28 },
   26     [4] = { .c = 0x0fffffe4, .b = 28 },
   27     [5] = { .c = 0x0fffffe5, .b = 28 },
   28     [6] = { .c = 0x0fffffe6, .b = 28 },
   29     [7] = { .c = 0x0fffffe7, .b = 28 },
   30     [8] = { .c = 0x0fffffe8, .b = 28 },
   31     [9] = { .c = 0x00ffffea, .b = 24 },
   32     [10] = { .c = 0x3ffffffc, .b = 30 },
   33     [11] = { .c = 0x0fffffe9, .b = 28 },
   34     [12] = { .c = 0x0fffffea, .b = 28 },
   35     [13] = { .c = 0x3ffffffd, .b = 30 },
   36     [14] = { .c = 0x0fffffeb, .b = 28 },
   37     [15] = { .c = 0x0fffffec, .b = 28 },
   38     [16] = { .c = 0x0fffffed, .b = 28 },
   39     [17] = { .c = 0x0fffffee, .b = 28 },
   40     [18] = { .c = 0x0fffffef, .b = 28 },
   41     [19] = { .c = 0x0ffffff0, .b = 28 },
   42     [20] = { .c = 0x0ffffff1, .b = 28 },
   43     [21] = { .c = 0x0ffffff2, .b = 28 },
   44     [22] = { .c = 0x3ffffffe, .b = 30 },
   45     [23] = { .c = 0x0ffffff3, .b = 28 },
   46     [24] = { .c = 0x0ffffff4, .b = 28 },
   47     [25] = { .c = 0x0ffffff5, .b = 28 },
   48     [26] = { .c = 0x0ffffff6, .b = 28 },
   49     [27] = { .c = 0x0ffffff7, .b = 28 },
   50     [28] = { .c = 0x0ffffff8, .b = 28 },
   51     [29] = { .c = 0x0ffffff9, .b = 28 },
   52     [30] = { .c = 0x0ffffffa, .b = 28 },
   53     [31] = { .c = 0x0ffffffb, .b = 28 },
   54     [32] = { .c = 0x00000014, .b =  6 },
   55     [33] = { .c = 0x000003f8, .b = 10 },
   56     [34] = { .c = 0x000003f9, .b = 10 },
   57     [35] = { .c = 0x00000ffa, .b = 12 },
   58     [36] = { .c = 0x00001ff9, .b = 13 },
   59     [37] = { .c = 0x00000015, .b =  6 },
   60     [38] = { .c = 0x000000f8, .b =  8 },
   61     [39] = { .c = 0x000007fa, .b = 11 },
   62     [40] = { .c = 0x000003fa, .b = 10 },
   63     [41] = { .c = 0x000003fb, .b = 10 },
   64     [42] = { .c = 0x000000f9, .b =  8 },
   65     [43] = { .c = 0x000007fb, .b = 11 },
   66     [44] = { .c = 0x000000fa, .b =  8 },
   67     [45] = { .c = 0x00000016, .b =  6 },
   68     [46] = { .c = 0x00000017, .b =  6 },
   69     [47] = { .c = 0x00000018, .b =  6 },
   70     [48] = { .c = 0x00000000, .b =  5 },
   71     [49] = { .c = 0x00000001, .b =  5 },
   72     [50] = { .c = 0x00000002, .b =  5 },
   73     [51] = { .c = 0x00000019, .b =  6 },
   74     [52] = { .c = 0x0000001a, .b =  6 },
   75     [53] = { .c = 0x0000001b, .b =  6 },
   76     [54] = { .c = 0x0000001c, .b =  6 },
   77     [55] = { .c = 0x0000001d, .b =  6 },
   78     [56] = { .c = 0x0000001e, .b =  6 },
   79     [57] = { .c = 0x0000001f, .b =  6 },
   80     [58] = { .c = 0x0000005c, .b =  7 },
   81     [59] = { .c = 0x000000fb, .b =  8 },
   82     [60] = { .c = 0x00007ffc, .b = 15 },
   83     [61] = { .c = 0x00000020, .b =  6 },
   84     [62] = { .c = 0x00000ffb, .b = 12 },
   85     [63] = { .c = 0x000003fc, .b = 10 },
   86     [64] = { .c = 0x00001ffa, .b = 13 },
   87     [65] = { .c = 0x00000021, .b =  6 },
   88     [66] = { .c = 0x0000005d, .b =  7 },
   89     [67] = { .c = 0x0000005e, .b =  7 },
   90     [68] = { .c = 0x0000005f, .b =  7 },
   91     [69] = { .c = 0x00000060, .b =  7 },
   92     [70] = { .c = 0x00000061, .b =  7 },
   93     [71] = { .c = 0x00000062, .b =  7 },
   94     [72] = { .c = 0x00000063, .b =  7 },
   95     [73] = { .c = 0x00000064, .b =  7 },
   96     [74] = { .c = 0x00000065, .b =  7 },
   97     [75] = { .c = 0x00000066, .b =  7 },
   98     [76] = { .c = 0x00000067, .b =  7 },
   99     [77] = { .c = 0x00000068, .b =  7 },
  100     [78] = { .c = 0x00000069, .b =  7 },
  101     [79] = { .c = 0x0000006a, .b =  7 },
  102     [80] = { .c = 0x0000006b, .b =  7 },
  103     [81] = { .c = 0x0000006c, .b =  7 },
  104     [82] = { .c = 0x0000006d, .b =  7 },
  105     [83] = { .c = 0x0000006e, .b =  7 },
  106     [84] = { .c = 0x0000006f, .b =  7 },
  107     [85] = { .c = 0x00000070, .b =  7 },
  108     [86] = { .c = 0x00000071, .b =  7 },
  109     [87] = { .c = 0x00000072, .b =  7 },
  110     [88] = { .c = 0x000000fc, .b =  8 },
  111     [89] = { .c = 0x00000073, .b =  7 },
  112     [90] = { .c = 0x000000fd, .b =  8 },
  113     [91] = { .c = 0x00001ffb, .b = 13 },
  114     [92] = { .c = 0x0007fff0, .b = 19 },
  115     [93] = { .c = 0x00001ffc, .b = 13 },
  116     [94] = { .c = 0x00003ffc, .b = 14 },
  117     [95] = { .c = 0x00000022, .b =  6 },
  118     [96] = { .c = 0x00007ffd, .b = 15 },
  119     [97] = { .c = 0x00000003, .b =  5 },
  120     [98] = { .c = 0x00000023, .b =  6 },
  121     [99] = { .c = 0x00000004, .b =  5 },
  122     [100] = { .c = 0x00000024, .b =  6 },
  123     [101] = { .c = 0x00000005, .b =  5 },
  124     [102] = { .c = 0x00000025, .b =  6 },
  125     [103] = { .c = 0x00000026, .b =  6 },
  126     [104] = { .c = 0x00000027, .b =  6 },
  127     [105] = { .c = 0x00000006, .b =  5 },
  128     [106] = { .c = 0x00000074, .b =  7 },
  129     [107] = { .c = 0x00000075, .b =  7 },
  130     [108] = { .c = 0x00000028, .b =  6 },
  131     [109] = { .c = 0x00000029, .b =  6 },
  132     [110] = { .c = 0x0000002a, .b =  6 },
  133     [111] = { .c = 0x00000007, .b =  5 },
  134     [112] = { .c = 0x0000002b, .b =  6 },
  135     [113] = { .c = 0x00000076, .b =  7 },
  136     [114] = { .c = 0x0000002c, .b =  6 },
  137     [115] = { .c = 0x00000008, .b =  5 },
  138     [116] = { .c = 0x00000009, .b =  5 },
  139     [117] = { .c = 0x0000002d, .b =  6 },
  140     [118] = { .c = 0x00000077, .b =  7 },
  141     [119] = { .c = 0x00000078, .b =  7 },
  142     [120] = { .c = 0x00000079, .b =  7 },
  143     [121] = { .c = 0x0000007a, .b =  7 },
  144     [122] = { .c = 0x0000007b, .b =  7 },
  145     [123] = { .c = 0x00007ffe, .b = 15 },
  146     [124] = { .c = 0x000007fc, .b = 11 },
  147     [125] = { .c = 0x00003ffd, .b = 14 },
  148     [126] = { .c = 0x00001ffd, .b = 13 },
  149     [127] = { .c = 0x0ffffffc, .b = 28 },
  150     [128] = { .c = 0x000fffe6, .b = 20 },
  151     [129] = { .c = 0x003fffd2, .b = 22 },
  152     [130] = { .c = 0x000fffe7, .b = 20 },
  153     [131] = { .c = 0x000fffe8, .b = 20 },
  154     [132] = { .c = 0x003fffd3, .b = 22 },
  155     [133] = { .c = 0x003fffd4, .b = 22 },
  156     [134] = { .c = 0x003fffd5, .b = 22 },
  157     [135] = { .c = 0x007fffd9, .b = 23 },
  158     [136] = { .c = 0x003fffd6, .b = 22 },
  159     [137] = { .c = 0x007fffda, .b = 23 },
  160     [138] = { .c = 0x007fffdb, .b = 23 },
  161     [139] = { .c = 0x007fffdc, .b = 23 },
  162     [140] = { .c = 0x007fffdd, .b = 23 },
  163     [141] = { .c = 0x007fffde, .b = 23 },
  164     [142] = { .c = 0x00ffffeb, .b = 24 },
  165     [143] = { .c = 0x007fffdf, .b = 23 },
  166     [144] = { .c = 0x00ffffec, .b = 24 },
  167     [145] = { .c = 0x00ffffed, .b = 24 },
  168     [146] = { .c = 0x003fffd7, .b = 22 },
  169     [147] = { .c = 0x007fffe0, .b = 23 },
  170     [148] = { .c = 0x00ffffee, .b = 24 },
  171     [149] = { .c = 0x007fffe1, .b = 23 },
  172     [150] = { .c = 0x007fffe2, .b = 23 },
  173     [151] = { .c = 0x007fffe3, .b = 23 },
  174     [152] = { .c = 0x007fffe4, .b = 23 },
  175     [153] = { .c = 0x001fffdc, .b = 21 },
  176     [154] = { .c = 0x003fffd8, .b = 22 },
  177     [155] = { .c = 0x007fffe5, .b = 23 },
  178     [156] = { .c = 0x003fffd9, .b = 22 },
  179     [157] = { .c = 0x007fffe6, .b = 23 },
  180     [158] = { .c = 0x007fffe7, .b = 23 },
  181     [159] = { .c = 0x00ffffef, .b = 24 },
  182     [160] = { .c = 0x003fffda, .b = 22 },
  183     [161] = { .c = 0x001fffdd, .b = 21 },
  184     [162] = { .c = 0x000fffe9, .b = 20 },
  185     [163] = { .c = 0x003fffdb, .b = 22 },
  186     [164] = { .c = 0x003fffdc, .b = 22 },
  187     [165] = { .c = 0x007fffe8, .b = 23 },
  188     [166] = { .c = 0x007fffe9, .b = 23 },
  189     [167] = { .c = 0x001fffde, .b = 21 },
  190     [168] = { .c = 0x007fffea, .b = 23 },
  191     [169] = { .c = 0x003fffdd, .b = 22 },
  192     [170] = { .c = 0x003fffde, .b = 22 },
  193     [171] = { .c = 0x00fffff0, .b = 24 },
  194     [172] = { .c = 0x001fffdf, .b = 21 },
  195     [173] = { .c = 0x003fffdf, .b = 22 },
  196     [174] = { .c = 0x007fffeb, .b = 23 },
  197     [175] = { .c = 0x007fffec, .b = 23 },
  198     [176] = { .c = 0x001fffe0, .b = 21 },
  199     [177] = { .c = 0x001fffe1, .b = 21 },
  200     [178] = { .c = 0x003fffe0, .b = 22 },
  201     [179] = { .c = 0x001fffe2, .b = 21 },
  202     [180] = { .c = 0x007fffed, .b = 23 },
  203     [181] = { .c = 0x003fffe1, .b = 22 },
  204     [182] = { .c = 0x007fffee, .b = 23 },
  205     [183] = { .c = 0x007fffef, .b = 23 },
  206     [184] = { .c = 0x000fffea, .b = 20 },
  207     [185] = { .c = 0x003fffe2, .b = 22 },
  208     [186] = { .c = 0x003fffe3, .b = 22 },
  209     [187] = { .c = 0x003fffe4, .b = 22 },
  210     [188] = { .c = 0x007ffff0, .b = 23 },
  211     [189] = { .c = 0x003fffe5, .b = 22 },
  212     [190] = { .c = 0x003fffe6, .b = 22 },
  213     [191] = { .c = 0x007ffff1, .b = 23 },
  214     [192] = { .c = 0x03ffffe0, .b = 26 },
  215     [193] = { .c = 0x03ffffe1, .b = 26 },
  216     [194] = { .c = 0x000fffeb, .b = 20 },
  217     [195] = { .c = 0x0007fff1, .b = 19 },
  218     [196] = { .c = 0x003fffe7, .b = 22 },
  219     [197] = { .c = 0x007ffff2, .b = 23 },
  220     [198] = { .c = 0x003fffe8, .b = 22 },
  221     [199] = { .c = 0x01ffffec, .b = 25 },
  222     [200] = { .c = 0x03ffffe2, .b = 26 },
  223     [201] = { .c = 0x03ffffe3, .b = 26 },
  224     [202] = { .c = 0x03ffffe4, .b = 26 },
  225     [203] = { .c = 0x07ffffde, .b = 27 },
  226     [204] = { .c = 0x07ffffdf, .b = 27 },
  227     [205] = { .c = 0x03ffffe5, .b = 26 },
  228     [206] = { .c = 0x00fffff1, .b = 24 },
  229     [207] = { .c = 0x01ffffed, .b = 25 },
  230     [208] = { .c = 0x0007fff2, .b = 19 },
  231     [209] = { .c = 0x001fffe3, .b = 21 },
  232     [210] = { .c = 0x03ffffe6, .b = 26 },
  233     [211] = { .c = 0x07ffffe0, .b = 27 },
  234     [212] = { .c = 0x07ffffe1, .b = 27 },
  235     [213] = { .c = 0x03ffffe7, .b = 26 },
  236     [214] = { .c = 0x07ffffe2, .b = 27 },
  237     [215] = { .c = 0x00fffff2, .b = 24 },
  238     [216] = { .c = 0x001fffe4, .b = 21 },
  239     [217] = { .c = 0x001fffe5, .b = 21 },
  240     [218] = { .c = 0x03ffffe8, .b = 26 },
  241     [219] = { .c = 0x03ffffe9, .b = 26 },
  242     [220] = { .c = 0x0ffffffd, .b = 28 },
  243     [221] = { .c = 0x07ffffe3, .b = 27 },
  244     [222] = { .c = 0x07ffffe4, .b = 27 },
  245     [223] = { .c = 0x07ffffe5, .b = 27 },
  246     [224] = { .c = 0x000fffec, .b = 20 },
  247     [225] = { .c = 0x00fffff3, .b = 24 },
  248     [226] = { .c = 0x000fffed, .b = 20 },
  249     [227] = { .c = 0x001fffe6, .b = 21 },
  250     [228] = { .c = 0x003fffe9, .b = 22 },
  251     [229] = { .c = 0x001fffe7, .b = 21 },
  252     [230] = { .c = 0x001fffe8, .b = 21 },
  253     [231] = { .c = 0x007ffff3, .b = 23 },
  254     [232] = { .c = 0x003fffea, .b = 22 },
  255     [233] = { .c = 0x003fffeb, .b = 22 },
  256     [234] = { .c = 0x01ffffee, .b = 25 },
  257     [235] = { .c = 0x01ffffef, .b = 25 },
  258     [236] = { .c = 0x00fffff4, .b = 24 },
  259     [237] = { .c = 0x00fffff5, .b = 24 },
  260     [238] = { .c = 0x03ffffea, .b = 26 },
  261     [239] = { .c = 0x007ffff4, .b = 23 },
  262     [240] = { .c = 0x03ffffeb, .b = 26 },
  263     [241] = { .c = 0x07ffffe6, .b = 27 },
  264     [242] = { .c = 0x03ffffec, .b = 26 },
  265     [243] = { .c = 0x03ffffed, .b = 26 },
  266     [244] = { .c = 0x07ffffe7, .b = 27 },
  267     [245] = { .c = 0x07ffffe8, .b = 27 },
  268     [246] = { .c = 0x07ffffe9, .b = 27 },
  269     [247] = { .c = 0x07ffffea, .b = 27 },
  270     [248] = { .c = 0x07ffffeb, .b = 27 },
  271     [249] = { .c = 0x0ffffffe, .b = 28 },
  272     [250] = { .c = 0x07ffffec, .b = 27 },
  273     [251] = { .c = 0x07ffffed, .b = 27 },
  274     [252] = { .c = 0x07ffffee, .b = 27 },
  275     [253] = { .c = 0x07ffffef, .b = 27 },
  276     [254] = { .c = 0x07fffff0, .b = 27 },
  277     [255] = { .c = 0x03ffffee, .b = 26 },
  278     [256] = { .c = 0x3fffffff, .b = 30 }, /* EOS */
  279 };
  280 
  281 
  282 int main(int argc, char **argv)
  283 {
  284     uint32_t c, i, j;
  285 
  286     /* fill first byte */
  287     printf("struct rht rht_bit31_24[256] = {\n");
  288     for (j = 0; j < 256; j++) {
  289         for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) {
  290             if (ht[i].b > 8)
  291                 continue;
  292             c = ht[i].c << (32 - ht[i].b);
  293 
  294             if (((c ^ (j << 24)) & -(1 << (32 - ht[i].b)) & 0xff000000) == 0) {
  295                 printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b);
  296                 break;
  297             }
  298         }
  299     }
  300     printf("};\n\n");
  301 
  302     printf("struct rht rht_bit24_17[256] = {\n");
  303     for (j = 0; j < 256; j++) {
  304         for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) {
  305             if (ht[i].b <= 8 || ht[i].b > 16)
  306                 continue;
  307             c = ht[i].c << (32 - ht[i].b);
  308 
  309             if (((c ^ (j << 17)) & -(1 << (32 - ht[i].b)) & 0x01fe0000) == 0) {
  310                 printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b);
  311                 break;
  312             }
  313         }
  314     }
  315     printf("};\n\n");
  316 
  317     printf("struct rht rht_bit15_11_fe[32] = {\n");
  318     for (j = 0; j < 32; j++) {
  319         for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) {
  320             if (ht[i].b <= 16 || ht[i].b > 21)
  321                 continue;
  322             c = ht[i].c << (32 - ht[i].b);
  323             if ((c & 0x00ff0000) != 0x00fe0000)
  324                 continue;
  325 
  326             if (((c ^ (j << 11)) & -(1 << (32 - ht[i].b)) & 0x0000f800) == 0) {
  327                 printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b);
  328                 break;
  329             }
  330         }
  331     }
  332     printf("};\n\n");
  333 
  334     printf("struct rht rht_bit15_8[256] = {\n");
  335     for (j = 0; j < 256; j++) {
  336         for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) {
  337             if (ht[i].b <= 16 || ht[i].b > 24)
  338                 continue;
  339             c = ht[i].c << (32 - ht[i].b);
  340             if ((c & 0x00ff0000) != 0x00ff0000)
  341                 continue;
  342 
  343             if (((c ^ (j << 8)) & -(1 << (32 - ht[i].b)) & 0x0000ff00) == 0) {
  344                 printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b);
  345                 break;
  346             }
  347         }
  348     }
  349     printf("};\n\n");
  350 
  351     printf("struct rht rht_bit11_4[256] = {\n");
  352     /* fill fourth byte after 0xff 0xff 0xf6-0xff. Only 0xfffffffx are not distinguished */
  353     for (j = 0; j < 256; j++) {
  354         for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) {
  355             if (ht[i].b <= 24)
  356                 continue;
  357             c = ht[i].c << (32 - ht[i].b);
  358 
  359             if (((c ^ (j << 4)) & -(1 << (32 - ht[i].b)) & 0x00000ff0) == 0) {
  360                 //printf("\tj=%02x i=%02x c=%08x l=%d c/l=%08x j/l=%08x xor=%08x\n", j, i, c, ht[i].b, c & -(1 << (32 - ht[i].b)), ((j << 4) & -(1 << (32 - ht[i].b))), (c ^ (j << 4)) & -(1 << (32 - ht[i].b)));
  361                 printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b);
  362                 break;
  363             }
  364         }
  365     }
  366     printf("\t/* Note, when l==30, bits 3..2 give 00:0x0a, 01:0x0d, 10:0x16, 11:EOS */\n");
  367     printf("};\n\n");
  368     return 0;
  369 }