Class: HTTP2::Header::Huffman

Inherits:
Object
  • Object
show all
Includes:
Error
Defined in:
lib/http/2/huffman.rb,
lib/http/2/huffman_statemachine.rb

Overview

Huffman encoder/decoder

Constant Summary collapse

BITS_AT_ONCE =
4
CODES =
[
  [0x1ff8, 13],
  [0x7fffd8, 23],
  [0xfffffe2, 28],
  [0xfffffe3, 28],
  [0xfffffe4, 28],
  [0xfffffe5, 28],
  [0xfffffe6, 28],
  [0xfffffe7, 28],
  [0xfffffe8, 28],
  [0xffffea, 24],
  [0x3ffffffc, 30],
  [0xfffffe9, 28],
  [0xfffffea, 28],
  [0x3ffffffd, 30],
  [0xfffffeb, 28],
  [0xfffffec, 28],
  [0xfffffed, 28],
  [0xfffffee, 28],
  [0xfffffef, 28],
  [0xffffff0, 28],
  [0xffffff1, 28],
  [0xffffff2, 28],
  [0x3ffffffe, 30],
  [0xffffff3, 28],
  [0xffffff4, 28],
  [0xffffff5, 28],
  [0xffffff6, 28],
  [0xffffff7, 28],
  [0xffffff8, 28],
  [0xffffff9, 28],
  [0xffffffa, 28],
  [0xffffffb, 28],
  [0x14,  6],
  [0x3f8, 10],
  [0x3f9, 10],
  [0xffa, 12],
  [0x1ff9, 13],
  [0x15,  6],
  [0xf8,  8],
  [0x7fa, 11],
  [0x3fa, 10],
  [0x3fb, 10],
  [0xf9,  8],
  [0x7fb, 11],
  [0xfa,  8],
  [0x16,  6],
  [0x17,  6],
  [0x18,  6],
  [0x0,  5],
  [0x1,  5],
  [0x2,  5],
  [0x19,  6],
  [0x1a,  6],
  [0x1b,  6],
  [0x1c,  6],
  [0x1d,  6],
  [0x1e,  6],
  [0x1f,  6],
  [0x5c,  7],
  [0xfb,  8],
  [0x7ffc, 15],
  [0x20,  6],
  [0xffb, 12],
  [0x3fc, 10],
  [0x1ffa, 13],
  [0x21,  6],
  [0x5d,  7],
  [0x5e,  7],
  [0x5f,  7],
  [0x60,  7],
  [0x61,  7],
  [0x62,  7],
  [0x63,  7],
  [0x64,  7],
  [0x65,  7],
  [0x66,  7],
  [0x67,  7],
  [0x68,  7],
  [0x69,  7],
  [0x6a,  7],
  [0x6b,  7],
  [0x6c,  7],
  [0x6d,  7],
  [0x6e,  7],
  [0x6f,  7],
  [0x70,  7],
  [0x71,  7],
  [0x72,  7],
  [0xfc,  8],
  [0x73,  7],
  [0xfd,  8],
  [0x1ffb, 13],
  [0x7fff0, 19],
  [0x1ffc, 13],
  [0x3ffc, 14],
  [0x22,  6],
  [0x7ffd, 15],
  [0x3,  5],
  [0x23,  6],
  [0x4,  5],
  [0x24,  6],
  [0x5,  5],
  [0x25,  6],
  [0x26,  6],
  [0x27,  6],
  [0x6,  5],
  [0x74,  7],
  [0x75,  7],
  [0x28,  6],
  [0x29,  6],
  [0x2a,  6],
  [0x7,  5],
  [0x2b,  6],
  [0x76,  7],
  [0x2c,  6],
  [0x8,  5],
  [0x9,  5],
  [0x2d,  6],
  [0x77,  7],
  [0x78,  7],
  [0x79,  7],
  [0x7a,  7],
  [0x7b,  7],
  [0x7ffe, 15],
  [0x7fc, 11],
  [0x3ffd, 14],
  [0x1ffd, 13],
  [0xffffffc, 28],
  [0xfffe6, 20],
  [0x3fffd2, 22],
  [0xfffe7, 20],
  [0xfffe8, 20],
  [0x3fffd3, 22],
  [0x3fffd4, 22],
  [0x3fffd5, 22],
  [0x7fffd9, 23],
  [0x3fffd6, 22],
  [0x7fffda, 23],
  [0x7fffdb, 23],
  [0x7fffdc, 23],
  [0x7fffdd, 23],
  [0x7fffde, 23],
  [0xffffeb, 24],
  [0x7fffdf, 23],
  [0xffffec, 24],
  [0xffffed, 24],
  [0x3fffd7, 22],
  [0x7fffe0, 23],
  [0xffffee, 24],
  [0x7fffe1, 23],
  [0x7fffe2, 23],
  [0x7fffe3, 23],
  [0x7fffe4, 23],
  [0x1fffdc, 21],
  [0x3fffd8, 22],
  [0x7fffe5, 23],
  [0x3fffd9, 22],
  [0x7fffe6, 23],
  [0x7fffe7, 23],
  [0xffffef, 24],
  [0x3fffda, 22],
  [0x1fffdd, 21],
  [0xfffe9, 20],
  [0x3fffdb, 22],
  [0x3fffdc, 22],
  [0x7fffe8, 23],
  [0x7fffe9, 23],
  [0x1fffde, 21],
  [0x7fffea, 23],
  [0x3fffdd, 22],
  [0x3fffde, 22],
  [0xfffff0, 24],
  [0x1fffdf, 21],
  [0x3fffdf, 22],
  [0x7fffeb, 23],
  [0x7fffec, 23],
  [0x1fffe0, 21],
  [0x1fffe1, 21],
  [0x3fffe0, 22],
  [0x1fffe2, 21],
  [0x7fffed, 23],
  [0x3fffe1, 22],
  [0x7fffee, 23],
  [0x7fffef, 23],
  [0xfffea, 20],
  [0x3fffe2, 22],
  [0x3fffe3, 22],
  [0x3fffe4, 22],
  [0x7ffff0, 23],
  [0x3fffe5, 22],
  [0x3fffe6, 22],
  [0x7ffff1, 23],
  [0x3ffffe0, 26],
  [0x3ffffe1, 26],
  [0xfffeb, 20],
  [0x7fff1, 19],
  [0x3fffe7, 22],
  [0x7ffff2, 23],
  [0x3fffe8, 22],
  [0x1ffffec, 25],
  [0x3ffffe2, 26],
  [0x3ffffe3, 26],
  [0x3ffffe4, 26],
  [0x7ffffde, 27],
  [0x7ffffdf, 27],
  [0x3ffffe5, 26],
  [0xfffff1, 24],
  [0x1ffffed, 25],
  [0x7fff2, 19],
  [0x1fffe3, 21],
  [0x3ffffe6, 26],
  [0x7ffffe0, 27],
  [0x7ffffe1, 27],
  [0x3ffffe7, 26],
  [0x7ffffe2, 27],
  [0xfffff2, 24],
  [0x1fffe4, 21],
  [0x1fffe5, 21],
  [0x3ffffe8, 26],
  [0x3ffffe9, 26],
  [0xffffffd, 28],
  [0x7ffffe3, 27],
  [0x7ffffe4, 27],
  [0x7ffffe5, 27],
  [0xfffec, 20],
  [0xfffff3, 24],
  [0xfffed, 20],
  [0x1fffe6, 21],
  [0x3fffe9, 22],
  [0x1fffe7, 21],
  [0x1fffe8, 21],
  [0x7ffff3, 23],
  [0x3fffea, 22],
  [0x3fffeb, 22],
  [0x1ffffee, 25],
  [0x1ffffef, 25],
  [0xfffff4, 24],
  [0xfffff5, 24],
  [0x3ffffea, 26],
  [0x7ffff4, 23],
  [0x3ffffeb, 26],
  [0x7ffffe6, 27],
  [0x3ffffec, 26],
  [0x3ffffed, 26],
  [0x7ffffe7, 27],
  [0x7ffffe8, 27],
  [0x7ffffe9, 27],
  [0x7ffffea, 27],
  [0x7ffffeb, 27],
  [0xffffffe, 28],
  [0x7ffffec, 27],
  [0x7ffffed, 27],
  [0x7ffffee, 27],
  [0x7ffffef, 27],
  [0x7fffff0, 27],
  [0x3ffffee, 26],
  [0x3fffffff, 30],
].each(&:freeze).freeze
ENCODE_TABLE =
CODES.map { |c, l| [c].pack('N').unpack('B*').first[-l..-1] }.each(&:freeze).freeze
MAX_FINAL_STATE =

:nodoc:

7
MACHINE =
[
  [[nil, 16], [nil, 76], [nil, 54], [nil, 36], [nil, 30], [nil, 28], [nil, 24], [nil, 221], [nil, 9], [nil, 10], [nil, 11], [nil, 12], [nil, 13], [nil, 14], [nil, 15], [nil, 1]],
  [[119, 29], [119, 5], [120, 29], [120, 5], [121, 29], [121, 5], [122, 29], [122, 5], [38, 0], [42, 0], [44, 0], [59, 0], [88, 0], [90, 0], [nil, 31], [nil, 32]],
  [[38, 29], [38, 5], [42, 29], [42, 5], [44, 29], [44, 5], [59, 29], [59, 5], [88, 29], [88, 5], [90, 29], [90, 5], [nil, 87], [nil, 88], [nil, 89], [nil, 90]],
  [[88, 25], [88, 26], [88, 27], [88, 6], [90, 25], [90, 26], [90, 27], [90, 6], [33, 0], [34, 0], [40, 0], [41, 0], [63, 0], [nil, 84], [nil, 85], [nil, 86]],
  [[33, 29], [33, 5], [34, 29], [34, 5], [40, 29], [40, 5], [41, 29], [41, 5], [63, 29], [63, 5], [39, 0], [43, 0], [124, 0], [nil, 81], [nil, 82], [nil, 83]],
  [[nil, 61], [nil, 62], [nil, 63], [nil, 64], [nil, 65], [nil, 66], [nil, 67], [nil, 68], [nil, 69], [nil, 70], [nil, 71], [nil, 72], [nil, 73], [nil, 74], [nil, 75], [nil, 2]],
  [[nil, 39], [nil, 40], [nil, 41], [nil, 42], [nil, 43], [nil, 44], [nil, 45], [nil, 46], [nil, 47], [nil, 48], [nil, 49], [nil, 50], [nil, 51], [nil, 52], [nil, 53], [nil, 3]],
  [[85, 0], [86, 0], [87, 0], [89, 0], [106, 0], [107, 0], [113, 0], [118, 0], [119, 0], [120, 0], [121, 0], [122, 0], [nil, 33], [nil, 34], [nil, 35], [nil, 4]],
  [[203, 17], [203, 18], [203, 19], [203, 20], [203, 21], [203, 22], [203, 23], [203, 7], [204, 17], [204, 18], [204, 19], [204, 20], [204, 21], [204, 22], [204, 23], [204, 7]],
  [[61, 25], [61, 26], [61, 27], [61, 6], [65, 25], [65, 26], [65, 27], [65, 6], [95, 25], [95, 26], [95, 27], [95, 6], [98, 25], [98, 26], [98, 27], [98, 6]],
  [[100, 25], [100, 26], [100, 27], [100, 6], [102, 25], [102, 26], [102, 27], [102, 6], [103, 25], [103, 26], [103, 27], [103, 6], [104, 25], [104, 26], [104, 27], [104, 6]],
  [[108, 25], [108, 26], [108, 27], [108, 6], [109, 25], [109, 26], [109, 27], [109, 6], [110, 25], [110, 26], [110, 27], [110, 6], [112, 25], [112, 26], [112, 27], [112, 6]],
  [[114, 25], [114, 26], [114, 27], [114, 6], [117, 25], [117, 26], [117, 27], [117, 6], [58, 29], [58, 5], [66, 29], [66, 5], [67, 29], [67, 5], [68, 29], [68, 5]],
  [[69, 29], [69, 5], [70, 29], [70, 5], [71, 29], [71, 5], [72, 29], [72, 5], [73, 29], [73, 5], [74, 29], [74, 5], [75, 29], [75, 5], [76, 29], [76, 5]],
  [[77, 29], [77, 5], [78, 29], [78, 5], [79, 29], [79, 5], [80, 29], [80, 5], [81, 29], [81, 5], [82, 29], [82, 5], [83, 29], [83, 5], [84, 29], [84, 5]],
  [[85, 29], [85, 5], [86, 29], [86, 5], [87, 29], [87, 5], [89, 29], [89, 5], [106, 29], [106, 5], [107, 29], [107, 5], [113, 29], [113, 5], [118, 29], [118, 5]],
  [[48, 17], [48, 18], [48, 19], [48, 20], [48, 21], [48, 22], [48, 23], [48, 7], [49, 17], [49, 18], [49, 19], [49, 20], [49, 21], [49, 22], [49, 23], [49, 7]],
  [[48, 25], [48, 26], [48, 27], [48, 6], [49, 25], [49, 26], [49, 27], [49, 6], [50, 25], [50, 26], [50, 27], [50, 6], [97, 25], [97, 26], [97, 27], [97, 6]],
  [[99, 25], [99, 26], [99, 27], [99, 6], [101, 25], [101, 26], [101, 27], [101, 6], [105, 25], [105, 26], [105, 27], [105, 6], [111, 25], [111, 26], [111, 27], [111, 6]],
  [[115, 25], [115, 26], [115, 27], [115, 6], [116, 25], [116, 26], [116, 27], [116, 6], [32, 29], [32, 5], [37, 29], [37, 5], [45, 29], [45, 5], [46, 29], [46, 5]],
  [[47, 29], [47, 5], [51, 29], [51, 5], [52, 29], [52, 5], [53, 29], [53, 5], [54, 29], [54, 5], [55, 29], [55, 5], [56, 29], [56, 5], [57, 29], [57, 5]],
  [[61, 29], [61, 5], [65, 29], [65, 5], [95, 29], [95, 5], [98, 29], [98, 5], [100, 29], [100, 5], [102, 29], [102, 5], [103, 29], [103, 5], [104, 29], [104, 5]],
  [[108, 29], [108, 5], [109, 29], [109, 5], [110, 29], [110, 5], [112, 29], [112, 5], [114, 29], [114, 5], [117, 29], [117, 5], [58, 0], [66, 0], [67, 0], [68, 0]],
  [[69, 0], [70, 0], [71, 0], [72, 0], [73, 0], [74, 0], [75, 0], [76, 0], [77, 0], [78, 0], [79, 0], [80, 0], [81, 0], [82, 0], [83, 0], [84, 0]],
  [[47, 25], [47, 26], [47, 27], [47, 6], [51, 25], [51, 26], [51, 27], [51, 6], [52, 25], [52, 26], [52, 27], [52, 6], [53, 25], [53, 26], [53, 27], [53, 6]],
  [[48, 29], [48, 5], [49, 29], [49, 5], [50, 29], [50, 5], [97, 29], [97, 5], [99, 29], [99, 5], [101, 29], [101, 5], [105, 29], [105, 5], [111, 29], [111, 5]],
  [[115, 29], [115, 5], [116, 29], [116, 5], [32, 0], [37, 0], [45, 0], [46, 0], [47, 0], [51, 0], [52, 0], [53, 0], [54, 0], [55, 0], [56, 0], [57, 0]],
  [[61, 0], [65, 0], [95, 0], [98, 0], [100, 0], [102, 0], [103, 0], [104, 0], [108, 0], [109, 0], [110, 0], [112, 0], [114, 0], [117, 0], [nil, 37], [nil, 38]],
  [[32, 25], [32, 26], [32, 27], [32, 6], [37, 25], [37, 26], [37, 27], [37, 6], [45, 25], [45, 26], [45, 27], [45, 6], [46, 25], [46, 26], [46, 27], [46, 6]],
  [[48, 0], [49, 0], [50, 0], [97, 0], [99, 0], [101, 0], [105, 0], [111, 0], [115, 0], [116, 0], [nil, 55], [nil, 56], [nil, 57], [nil, 58], [nil, 59], [nil, 60]],
  [[115, 17], [115, 18], [115, 19], [115, 20], [115, 21], [115, 22], [115, 23], [115, 7], [116, 17], [116, 18], [116, 19], [116, 20], [116, 21], [116, 22], [116, 23], [116, 7]],
  [[33, 25], [33, 26], [33, 27], [33, 6], [34, 25], [34, 26], [34, 27], [34, 6], [40, 25], [40, 26], [40, 27], [40, 6], [41, 25], [41, 26], [41, 27], [41, 6]],
  [[63, 25], [63, 26], [63, 27], [63, 6], [39, 29], [39, 5], [43, 29], [43, 5], [124, 29], [124, 5], [35, 0], [62, 0], [nil, 77], [nil, 78], [nil, 79], [nil, 80]],
  [[38, 17], [38, 18], [38, 19], [38, 20], [38, 21], [38, 22], [38, 23], [38, 7], [42, 17], [42, 18], [42, 19], [42, 20], [42, 21], [42, 22], [42, 23], [42, 7]],
  [[44, 17], [44, 18], [44, 19], [44, 20], [44, 21], [44, 22], [44, 23], [44, 7], [59, 17], [59, 18], [59, 19], [59, 20], [59, 21], [59, 22], [59, 23], [59, 7]],
  [[88, 17], [88, 18], [88, 19], [88, 20], [88, 21], [88, 22], [88, 23], [88, 7], [90, 17], [90, 18], [90, 19], [90, 20], [90, 21], [90, 22], [90, 23], [90, 7]],
  [[105, 17], [105, 18], [105, 19], [105, 20], [105, 21], [105, 22], [105, 23], [105, 7], [111, 17], [111, 18], [111, 19], [111, 20], [111, 21], [111, 22], [111, 23], [111, 7]],
  [[58, 17], [58, 18], [58, 19], [58, 20], [58, 21], [58, 22], [58, 23], [58, 7], [66, 17], [66, 18], [66, 19], [66, 20], [66, 21], [66, 22], [66, 23], [66, 7]],
  [[67, 17], [67, 18], [67, 19], [67, 20], [67, 21], [67, 22], [67, 23], [67, 7], [68, 17], [68, 18], [68, 19], [68, 20], [68, 21], [68, 22], [68, 23], [68, 7]],
  [[69, 17], [69, 18], [69, 19], [69, 20], [69, 21], [69, 22], [69, 23], [69, 7], [70, 17], [70, 18], [70, 19], [70, 20], [70, 21], [70, 22], [70, 23], [70, 7]],
  [[71, 17], [71, 18], [71, 19], [71, 20], [71, 21], [71, 22], [71, 23], [71, 7], [72, 17], [72, 18], [72, 19], [72, 20], [72, 21], [72, 22], [72, 23], [72, 7]],
  [[73, 17], [73, 18], [73, 19], [73, 20], [73, 21], [73, 22], [73, 23], [73, 7], [74, 17], [74, 18], [74, 19], [74, 20], [74, 21], [74, 22], [74, 23], [74, 7]],
  [[75, 17], [75, 18], [75, 19], [75, 20], [75, 21], [75, 22], [75, 23], [75, 7], [76, 17], [76, 18], [76, 19], [76, 20], [76, 21], [76, 22], [76, 23], [76, 7]],
  [[77, 17], [77, 18], [77, 19], [77, 20], [77, 21], [77, 22], [77, 23], [77, 7], [78, 17], [78, 18], [78, 19], [78, 20], [78, 21], [78, 22], [78, 23], [78, 7]],
  [[79, 17], [79, 18], [79, 19], [79, 20], [79, 21], [79, 22], [79, 23], [79, 7], [80, 17], [80, 18], [80, 19], [80, 20], [80, 21], [80, 22], [80, 23], [80, 7]],
  [[81, 17], [81, 18], [81, 19], [81, 20], [81, 21], [81, 22], [81, 23], [81, 7], [82, 17], [82, 18], [82, 19], [82, 20], [82, 21], [82, 22], [82, 23], [82, 7]],
  [[83, 17], [83, 18], [83, 19], [83, 20], [83, 21], [83, 22], [83, 23], [83, 7], [84, 17], [84, 18], [84, 19], [84, 20], [84, 21], [84, 22], [84, 23], [84, 7]],
  [[85, 17], [85, 18], [85, 19], [85, 20], [85, 21], [85, 22], [85, 23], [85, 7], [86, 17], [86, 18], [86, 19], [86, 20], [86, 21], [86, 22], [86, 23], [86, 7]],
  [[87, 17], [87, 18], [87, 19], [87, 20], [87, 21], [87, 22], [87, 23], [87, 7], [89, 17], [89, 18], [89, 19], [89, 20], [89, 21], [89, 22], [89, 23], [89, 7]],
  [[106, 17], [106, 18], [106, 19], [106, 20], [106, 21], [106, 22], [106, 23], [106, 7], [107, 17], [107, 18], [107, 19], [107, 20], [107, 21], [107, 22], [107, 23], [107, 7]],
  [[113, 17], [113, 18], [113, 19], [113, 20], [113, 21], [113, 22], [113, 23], [113, 7], [118, 17], [118, 18], [118, 19], [118, 20], [118, 21], [118, 22], [118, 23], [118, 7]],
  [[119, 17], [119, 18], [119, 19], [119, 20], [119, 21], [119, 22], [119, 23], [119, 7], [120, 17], [120, 18], [120, 19], [120, 20], [120, 21], [120, 22], [120, 23], [120, 7]],
  [[121, 17], [121, 18], [121, 19], [121, 20], [121, 21], [121, 22], [121, 23], [121, 7], [122, 17], [122, 18], [122, 19], [122, 20], [122, 21], [122, 22], [122, 23], [122, 7]],
  [[38, 25], [38, 26], [38, 27], [38, 6], [42, 25], [42, 26], [42, 27], [42, 6], [44, 25], [44, 26], [44, 27], [44, 6], [59, 25], [59, 26], [59, 27], [59, 6]],
  [[99, 17], [99, 18], [99, 19], [99, 20], [99, 21], [99, 22], [99, 23], [99, 7], [101, 17], [101, 18], [101, 19], [101, 20], [101, 21], [101, 22], [101, 23], [101, 7]],
  [[32, 17], [32, 18], [32, 19], [32, 20], [32, 21], [32, 22], [32, 23], [32, 7], [37, 17], [37, 18], [37, 19], [37, 20], [37, 21], [37, 22], [37, 23], [37, 7]],
  [[45, 17], [45, 18], [45, 19], [45, 20], [45, 21], [45, 22], [45, 23], [45, 7], [46, 17], [46, 18], [46, 19], [46, 20], [46, 21], [46, 22], [46, 23], [46, 7]],
  [[47, 17], [47, 18], [47, 19], [47, 20], [47, 21], [47, 22], [47, 23], [47, 7], [51, 17], [51, 18], [51, 19], [51, 20], [51, 21], [51, 22], [51, 23], [51, 7]],
  [[52, 17], [52, 18], [52, 19], [52, 20], [52, 21], [52, 22], [52, 23], [52, 7], [53, 17], [53, 18], [53, 19], [53, 20], [53, 21], [53, 22], [53, 23], [53, 7]],
  [[54, 17], [54, 18], [54, 19], [54, 20], [54, 21], [54, 22], [54, 23], [54, 7], [55, 17], [55, 18], [55, 19], [55, 20], [55, 21], [55, 22], [55, 23], [55, 7]],
  [[56, 17], [56, 18], [56, 19], [56, 20], [56, 21], [56, 22], [56, 23], [56, 7], [57, 17], [57, 18], [57, 19], [57, 20], [57, 21], [57, 22], [57, 23], [57, 7]],
  [[61, 17], [61, 18], [61, 19], [61, 20], [61, 21], [61, 22], [61, 23], [61, 7], [65, 17], [65, 18], [65, 19], [65, 20], [65, 21], [65, 22], [65, 23], [65, 7]],
  [[95, 17], [95, 18], [95, 19], [95, 20], [95, 21], [95, 22], [95, 23], [95, 7], [98, 17], [98, 18], [98, 19], [98, 20], [98, 21], [98, 22], [98, 23], [98, 7]],
  [[100, 17], [100, 18], [100, 19], [100, 20], [100, 21], [100, 22], [100, 23], [100, 7], [102, 17], [102, 18], [102, 19], [102, 20], [102, 21], [102, 22], [102, 23], [102, 7]],
  [[103, 17], [103, 18], [103, 19], [103, 20], [103, 21], [103, 22], [103, 23], [103, 7], [104, 17], [104, 18], [104, 19], [104, 20], [104, 21], [104, 22], [104, 23], [104, 7]],
  [[108, 17], [108, 18], [108, 19], [108, 20], [108, 21], [108, 22], [108, 23], [108, 7], [109, 17], [109, 18], [109, 19], [109, 20], [109, 21], [109, 22], [109, 23], [109, 7]],
  [[110, 17], [110, 18], [110, 19], [110, 20], [110, 21], [110, 22], [110, 23], [110, 7], [112, 17], [112, 18], [112, 19], [112, 20], [112, 21], [112, 22], [112, 23], [112, 7]],
  [[114, 17], [114, 18], [114, 19], [114, 20], [114, 21], [114, 22], [114, 23], [114, 7], [117, 17], [117, 18], [117, 19], [117, 20], [117, 21], [117, 22], [117, 23], [117, 7]],
  [[58, 25], [58, 26], [58, 27], [58, 6], [66, 25], [66, 26], [66, 27], [66, 6], [67, 25], [67, 26], [67, 27], [67, 6], [68, 25], [68, 26], [68, 27], [68, 6]],
  [[69, 25], [69, 26], [69, 27], [69, 6], [70, 25], [70, 26], [70, 27], [70, 6], [71, 25], [71, 26], [71, 27], [71, 6], [72, 25], [72, 26], [72, 27], [72, 6]],
  [[73, 25], [73, 26], [73, 27], [73, 6], [74, 25], [74, 26], [74, 27], [74, 6], [75, 25], [75, 26], [75, 27], [75, 6], [76, 25], [76, 26], [76, 27], [76, 6]],
  [[77, 25], [77, 26], [77, 27], [77, 6], [78, 25], [78, 26], [78, 27], [78, 6], [79, 25], [79, 26], [79, 27], [79, 6], [80, 25], [80, 26], [80, 27], [80, 6]],
  [[81, 25], [81, 26], [81, 27], [81, 6], [82, 25], [82, 26], [82, 27], [82, 6], [83, 25], [83, 26], [83, 27], [83, 6], [84, 25], [84, 26], [84, 27], [84, 6]],
  [[85, 25], [85, 26], [85, 27], [85, 6], [86, 25], [86, 26], [86, 27], [86, 6], [87, 25], [87, 26], [87, 27], [87, 6], [89, 25], [89, 26], [89, 27], [89, 6]],
  [[106, 25], [106, 26], [106, 27], [106, 6], [107, 25], [107, 26], [107, 27], [107, 6], [113, 25], [113, 26], [113, 27], [113, 6], [118, 25], [118, 26], [118, 27], [118, 6]],
  [[119, 25], [119, 26], [119, 27], [119, 6], [120, 25], [120, 26], [120, 27], [120, 6], [121, 25], [121, 26], [121, 27], [121, 6], [122, 25], [122, 26], [122, 27], [122, 6]],
  [[50, 17], [50, 18], [50, 19], [50, 20], [50, 21], [50, 22], [50, 23], [50, 7], [97, 17], [97, 18], [97, 19], [97, 20], [97, 21], [97, 22], [97, 23], [97, 7]],
  [[0, 17], [0, 18], [0, 19], [0, 20], [0, 21], [0, 22], [0, 23], [0, 7], [36, 17], [36, 18], [36, 19], [36, 20], [36, 21], [36, 22], [36, 23], [36, 7]],
  [[64, 17], [64, 18], [64, 19], [64, 20], [64, 21], [64, 22], [64, 23], [64, 7], [91, 17], [91, 18], [91, 19], [91, 20], [91, 21], [91, 22], [91, 23], [91, 7]],
  [[93, 17], [93, 18], [93, 19], [93, 20], [93, 21], [93, 22], [93, 23], [93, 7], [126, 17], [126, 18], [126, 19], [126, 20], [126, 21], [126, 22], [126, 23], [126, 7]],
  [[94, 25], [94, 26], [94, 27], [94, 6], [125, 25], [125, 26], [125, 27], [125, 6], [60, 29], [60, 5], [96, 29], [96, 5], [123, 29], [123, 5], [nil, 91], [nil, 92]],
  [[35, 17], [35, 18], [35, 19], [35, 20], [35, 21], [35, 22], [35, 23], [35, 7], [62, 17], [62, 18], [62, 19], [62, 20], [62, 21], [62, 22], [62, 23], [62, 7]],
  [[0, 25], [0, 26], [0, 27], [0, 6], [36, 25], [36, 26], [36, 27], [36, 6], [64, 25], [64, 26], [64, 27], [64, 6], [91, 25], [91, 26], [91, 27], [91, 6]],
  [[93, 25], [93, 26], [93, 27], [93, 6], [126, 25], [126, 26], [126, 27], [126, 6], [94, 29], [94, 5], [125, 29], [125, 5], [60, 0], [96, 0], [123, 0], [nil, 93]],
  [[39, 17], [39, 18], [39, 19], [39, 20], [39, 21], [39, 22], [39, 23], [39, 7], [43, 17], [43, 18], [43, 19], [43, 20], [43, 21], [43, 22], [43, 23], [43, 7]],
  [[124, 17], [124, 18], [124, 19], [124, 20], [124, 21], [124, 22], [124, 23], [124, 7], [35, 25], [35, 26], [35, 27], [35, 6], [62, 25], [62, 26], [62, 27], [62, 6]],
  [[0, 29], [0, 5], [36, 29], [36, 5], [64, 29], [64, 5], [91, 29], [91, 5], [93, 29], [93, 5], [126, 29], [126, 5], [94, 0], [125, 0], [nil, 94], [nil, 95]],
  [[33, 17], [33, 18], [33, 19], [33, 20], [33, 21], [33, 22], [33, 23], [33, 7], [34, 17], [34, 18], [34, 19], [34, 20], [34, 21], [34, 22], [34, 23], [34, 7]],
  [[40, 17], [40, 18], [40, 19], [40, 20], [40, 21], [40, 22], [40, 23], [40, 7], [41, 17], [41, 18], [41, 19], [41, 20], [41, 21], [41, 22], [41, 23], [41, 7]],
  [[63, 17], [63, 18], [63, 19], [63, 20], [63, 21], [63, 22], [63, 23], [63, 7], [39, 25], [39, 26], [39, 27], [39, 6], [43, 25], [43, 26], [43, 27], [43, 6]],
  [[124, 25], [124, 26], [124, 27], [124, 6], [35, 29], [35, 5], [62, 29], [62, 5], [0, 0], [36, 0], [64, 0], [91, 0], [93, 0], [126, 0], [nil, 96], [nil, 97]],
  [[92, 29], [92, 5], [195, 29], [195, 5], [208, 29], [208, 5], [128, 0], [130, 0], [131, 0], [162, 0], [184, 0], [194, 0], [224, 0], [226, 0], [nil, 98], [nil, 99]],
  [[nil, 100], [nil, 101], [nil, 102], [nil, 103], [nil, 104], [nil, 105], [nil, 106], [nil, 107], [nil, 108], [nil, 109], [nil, 110], [nil, 111], [nil, 112], [nil, 113], [nil, 114], [nil, 115]],
  [[92, 0], [195, 0], [208, 0], [nil, 116], [nil, 117], [nil, 118], [nil, 119], [nil, 120], [nil, 121], [nil, 122], [nil, 123], [nil, 124], [nil, 125], [nil, 126], [nil, 127], [nil, 128]],
  [[60, 17], [60, 18], [60, 19], [60, 20], [60, 21], [60, 22], [60, 23], [60, 7], [96, 17], [96, 18], [96, 19], [96, 20], [96, 21], [96, 22], [96, 23], [96, 7]],
  [[123, 17], [123, 18], [123, 19], [123, 20], [123, 21], [123, 22], [123, 23], [123, 7], [nil, 129], [nil, 130], [nil, 131], [nil, 132], [nil, 133], [nil, 134], [nil, 135], [nil, 136]],
  [[94, 17], [94, 18], [94, 19], [94, 20], [94, 21], [94, 22], [94, 23], [94, 7], [125, 17], [125, 18], [125, 19], [125, 20], [125, 21], [125, 22], [125, 23], [125, 7]],
  [[60, 25], [60, 26], [60, 27], [60, 6], [96, 25], [96, 26], [96, 27], [96, 6], [123, 25], [123, 26], [123, 27], [123, 6], [nil, 137], [nil, 138], [nil, 139], [nil, 140]],
  [[153, 17], [153, 18], [153, 19], [153, 20], [153, 21], [153, 22], [153, 23], [153, 7], [161, 17], [161, 18], [161, 19], [161, 20], [161, 21], [161, 22], [161, 23], [161, 7]],
  [[167, 17], [167, 18], [167, 19], [167, 20], [167, 21], [167, 22], [167, 23], [167, 7], [172, 17], [172, 18], [172, 19], [172, 20], [172, 21], [172, 22], [172, 23], [172, 7]],
  [[176, 17], [176, 18], [176, 19], [176, 20], [176, 21], [176, 22], [176, 23], [176, 7], [177, 17], [177, 18], [177, 19], [177, 20], [177, 21], [177, 22], [177, 23], [177, 7]],
  [[179, 17], [179, 18], [179, 19], [179, 20], [179, 21], [179, 22], [179, 23], [179, 7], [209, 17], [209, 18], [209, 19], [209, 20], [209, 21], [209, 22], [209, 23], [209, 7]],
  [[216, 17], [216, 18], [216, 19], [216, 20], [216, 21], [216, 22], [216, 23], [216, 7], [217, 17], [217, 18], [217, 19], [217, 20], [217, 21], [217, 22], [217, 23], [217, 7]],
  [[227, 17], [227, 18], [227, 19], [227, 20], [227, 21], [227, 22], [227, 23], [227, 7], [229, 17], [229, 18], [229, 19], [229, 20], [229, 21], [229, 22], [229, 23], [229, 7]],
  [[230, 17], [230, 18], [230, 19], [230, 20], [230, 21], [230, 22], [230, 23], [230, 7], [129, 25], [129, 26], [129, 27], [129, 6], [132, 25], [132, 26], [132, 27], [132, 6]],
  [[133, 25], [133, 26], [133, 27], [133, 6], [134, 25], [134, 26], [134, 27], [134, 6], [136, 25], [136, 26], [136, 27], [136, 6], [146, 25], [146, 26], [146, 27], [146, 6]],
  [[154, 25], [154, 26], [154, 27], [154, 6], [156, 25], [156, 26], [156, 27], [156, 6], [160, 25], [160, 26], [160, 27], [160, 6], [163, 25], [163, 26], [163, 27], [163, 6]],
  [[164, 25], [164, 26], [164, 27], [164, 6], [169, 25], [169, 26], [169, 27], [169, 6], [170, 25], [170, 26], [170, 27], [170, 6], [173, 25], [173, 26], [173, 27], [173, 6]],
  [[178, 25], [178, 26], [178, 27], [178, 6], [181, 25], [181, 26], [181, 27], [181, 6], [185, 25], [185, 26], [185, 27], [185, 6], [186, 25], [186, 26], [186, 27], [186, 6]],
  [[187, 25], [187, 26], [187, 27], [187, 6], [189, 25], [189, 26], [189, 27], [189, 6], [190, 25], [190, 26], [190, 27], [190, 6], [196, 25], [196, 26], [196, 27], [196, 6]],
  [[198, 25], [198, 26], [198, 27], [198, 6], [228, 25], [228, 26], [228, 27], [228, 6], [232, 25], [232, 26], [232, 27], [232, 6], [233, 25], [233, 26], [233, 27], [233, 6]],
  [[1, 29], [1, 5], [135, 29], [135, 5], [137, 29], [137, 5], [138, 29], [138, 5], [139, 29], [139, 5], [140, 29], [140, 5], [141, 29], [141, 5], [143, 29], [143, 5]],
  [[147, 29], [147, 5], [149, 29], [149, 5], [150, 29], [150, 5], [151, 29], [151, 5], [152, 29], [152, 5], [155, 29], [155, 5], [157, 29], [157, 5], [158, 29], [158, 5]],
  [[165, 29], [165, 5], [166, 29], [166, 5], [168, 29], [168, 5], [174, 29], [174, 5], [175, 29], [175, 5], [180, 29], [180, 5], [182, 29], [182, 5], [183, 29], [183, 5]],
  [[188, 29], [188, 5], [191, 29], [191, 5], [197, 29], [197, 5], [231, 29], [231, 5], [239, 29], [239, 5], [9, 0], [142, 0], [144, 0], [145, 0], [148, 0], [159, 0]],
  [[171, 0], [206, 0], [215, 0], [225, 0], [236, 0], [237, 0], [nil, 141], [nil, 142], [nil, 143], [nil, 144], [nil, 145], [nil, 146], [nil, 147], [nil, 148], [nil, 149], [nil, 150]],
  [[128, 17], [128, 18], [128, 19], [128, 20], [128, 21], [128, 22], [128, 23], [128, 7], [130, 17], [130, 18], [130, 19], [130, 20], [130, 21], [130, 22], [130, 23], [130, 7]],
  [[131, 17], [131, 18], [131, 19], [131, 20], [131, 21], [131, 22], [131, 23], [131, 7], [162, 17], [162, 18], [162, 19], [162, 20], [162, 21], [162, 22], [162, 23], [162, 7]],
  [[184, 17], [184, 18], [184, 19], [184, 20], [184, 21], [184, 22], [184, 23], [184, 7], [194, 17], [194, 18], [194, 19], [194, 20], [194, 21], [194, 22], [194, 23], [194, 7]],
  [[224, 17], [224, 18], [224, 19], [224, 20], [224, 21], [224, 22], [224, 23], [224, 7], [226, 17], [226, 18], [226, 19], [226, 20], [226, 21], [226, 22], [226, 23], [226, 7]],
  [[153, 25], [153, 26], [153, 27], [153, 6], [161, 25], [161, 26], [161, 27], [161, 6], [167, 25], [167, 26], [167, 27], [167, 6], [172, 25], [172, 26], [172, 27], [172, 6]],
  [[176, 25], [176, 26], [176, 27], [176, 6], [177, 25], [177, 26], [177, 27], [177, 6], [179, 25], [179, 26], [179, 27], [179, 6], [209, 25], [209, 26], [209, 27], [209, 6]],
  [[216, 25], [216, 26], [216, 27], [216, 6], [217, 25], [217, 26], [217, 27], [217, 6], [227, 25], [227, 26], [227, 27], [227, 6], [229, 25], [229, 26], [229, 27], [229, 6]],
  [[230, 25], [230, 26], [230, 27], [230, 6], [129, 29], [129, 5], [132, 29], [132, 5], [133, 29], [133, 5], [134, 29], [134, 5], [136, 29], [136, 5], [146, 29], [146, 5]],
  [[154, 29], [154, 5], [156, 29], [156, 5], [160, 29], [160, 5], [163, 29], [163, 5], [164, 29], [164, 5], [169, 29], [169, 5], [170, 29], [170, 5], [173, 29], [173, 5]],
  [[178, 29], [178, 5], [181, 29], [181, 5], [185, 29], [185, 5], [186, 29], [186, 5], [187, 29], [187, 5], [189, 29], [189, 5], [190, 29], [190, 5], [196, 29], [196, 5]],
  [[198, 29], [198, 5], [228, 29], [228, 5], [232, 29], [232, 5], [233, 29], [233, 5], [1, 0], [135, 0], [137, 0], [138, 0], [139, 0], [140, 0], [141, 0], [143, 0]],
  [[147, 0], [149, 0], [150, 0], [151, 0], [152, 0], [155, 0], [157, 0], [158, 0], [165, 0], [166, 0], [168, 0], [174, 0], [175, 0], [180, 0], [182, 0], [183, 0]],
  [[188, 0], [191, 0], [197, 0], [231, 0], [239, 0], [nil, 151], [nil, 152], [nil, 153], [nil, 154], [nil, 155], [nil, 156], [nil, 157], [nil, 158], [nil, 159], [nil, 160], [nil, 161]],
  [[92, 17], [92, 18], [92, 19], [92, 20], [92, 21], [92, 22], [92, 23], [92, 7], [195, 17], [195, 18], [195, 19], [195, 20], [195, 21], [195, 22], [195, 23], [195, 7]],
  [[208, 17], [208, 18], [208, 19], [208, 20], [208, 21], [208, 22], [208, 23], [208, 7], [128, 25], [128, 26], [128, 27], [128, 6], [130, 25], [130, 26], [130, 27], [130, 6]],
  [[131, 25], [131, 26], [131, 27], [131, 6], [162, 25], [162, 26], [162, 27], [162, 6], [184, 25], [184, 26], [184, 27], [184, 6], [194, 25], [194, 26], [194, 27], [194, 6]],
  [[224, 25], [224, 26], [224, 27], [224, 6], [226, 25], [226, 26], [226, 27], [226, 6], [153, 29], [153, 5], [161, 29], [161, 5], [167, 29], [167, 5], [172, 29], [172, 5]],
  [[176, 29], [176, 5], [177, 29], [177, 5], [179, 29], [179, 5], [209, 29], [209, 5], [216, 29], [216, 5], [217, 29], [217, 5], [227, 29], [227, 5], [229, 29], [229, 5]],
  [[230, 29], [230, 5], [129, 0], [132, 0], [133, 0], [134, 0], [136, 0], [146, 0], [154, 0], [156, 0], [160, 0], [163, 0], [164, 0], [169, 0], [170, 0], [173, 0]],
  [[178, 0], [181, 0], [185, 0], [186, 0], [187, 0], [189, 0], [190, 0], [196, 0], [198, 0], [228, 0], [232, 0], [233, 0], [nil, 162], [nil, 163], [nil, 164], [nil, 165]],
  [[nil, 166], [nil, 167], [nil, 168], [nil, 169], [nil, 170], [nil, 171], [nil, 172], [nil, 173], [nil, 174], [nil, 175], [nil, 176], [nil, 177], [nil, 178], [nil, 179], [nil, 180], [nil, 181]],
  [[92, 25], [92, 26], [92, 27], [92, 6], [195, 25], [195, 26], [195, 27], [195, 6], [208, 25], [208, 26], [208, 27], [208, 6], [128, 29], [128, 5], [130, 29], [130, 5]],
  [[131, 29], [131, 5], [162, 29], [162, 5], [184, 29], [184, 5], [194, 29], [194, 5], [224, 29], [224, 5], [226, 29], [226, 5], [153, 0], [161, 0], [167, 0], [172, 0]],
  [[176, 0], [177, 0], [179, 0], [209, 0], [216, 0], [217, 0], [227, 0], [229, 0], [230, 0], [nil, 182], [nil, 183], [nil, 184], [nil, 185], [nil, 186], [nil, 187], [nil, 188]],
  [[nil, 189], [nil, 190], [nil, 191], [nil, 192], [nil, 193], [nil, 194], [nil, 195], [nil, 196], [nil, 197], [nil, 198], [nil, 199], [nil, 200], [nil, 201], [nil, 202], [nil, 203], [nil, 204]],
  [[199, 17], [199, 18], [199, 19], [199, 20], [199, 21], [199, 22], [199, 23], [199, 7], [207, 17], [207, 18], [207, 19], [207, 20], [207, 21], [207, 22], [207, 23], [207, 7]],
  [[234, 17], [234, 18], [234, 19], [234, 20], [234, 21], [234, 22], [234, 23], [234, 7], [235, 17], [235, 18], [235, 19], [235, 20], [235, 21], [235, 22], [235, 23], [235, 7]],
  [[192, 25], [192, 26], [192, 27], [192, 6], [193, 25], [193, 26], [193, 27], [193, 6], [200, 25], [200, 26], [200, 27], [200, 6], [201, 25], [201, 26], [201, 27], [201, 6]],
  [[202, 25], [202, 26], [202, 27], [202, 6], [205, 25], [205, 26], [205, 27], [205, 6], [210, 25], [210, 26], [210, 27], [210, 6], [213, 25], [213, 26], [213, 27], [213, 6]],
  [[218, 25], [218, 26], [218, 27], [218, 6], [219, 25], [219, 26], [219, 27], [219, 6], [238, 25], [238, 26], [238, 27], [238, 6], [240, 25], [240, 26], [240, 27], [240, 6]],
  [[242, 25], [242, 26], [242, 27], [242, 6], [243, 25], [243, 26], [243, 27], [243, 6], [255, 25], [255, 26], [255, 27], [255, 6], [203, 29], [203, 5], [204, 29], [204, 5]],
  [[211, 29], [211, 5], [212, 29], [212, 5], [214, 29], [214, 5], [221, 29], [221, 5], [222, 29], [222, 5], [223, 29], [223, 5], [241, 29], [241, 5], [244, 29], [244, 5]],
  [[245, 29], [245, 5], [246, 29], [246, 5], [247, 29], [247, 5], [248, 29], [248, 5], [250, 29], [250, 5], [251, 29], [251, 5], [252, 29], [252, 5], [253, 29], [253, 5]],
  [[254, 29], [254, 5], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0], [8, 0], [11, 0], [12, 0], [14, 0], [15, 0], [16, 0], [17, 0], [18, 0]],
  [[19, 0], [20, 0], [21, 0], [23, 0], [24, 0], [25, 0], [26, 0], [27, 0], [28, 0], [29, 0], [30, 0], [31, 0], [127, 0], [220, 0], [249, 0], [nil, 205]],
  [[9, 17], [9, 18], [9, 19], [9, 20], [9, 21], [9, 22], [9, 23], [9, 7], [142, 17], [142, 18], [142, 19], [142, 20], [142, 21], [142, 22], [142, 23], [142, 7]],
  [[144, 17], [144, 18], [144, 19], [144, 20], [144, 21], [144, 22], [144, 23], [144, 7], [145, 17], [145, 18], [145, 19], [145, 20], [145, 21], [145, 22], [145, 23], [145, 7]],
  [[148, 17], [148, 18], [148, 19], [148, 20], [148, 21], [148, 22], [148, 23], [148, 7], [159, 17], [159, 18], [159, 19], [159, 20], [159, 21], [159, 22], [159, 23], [159, 7]],
  [[171, 17], [171, 18], [171, 19], [171, 20], [171, 21], [171, 22], [171, 23], [171, 7], [206, 17], [206, 18], [206, 19], [206, 20], [206, 21], [206, 22], [206, 23], [206, 7]],
  [[215, 17], [215, 18], [215, 19], [215, 20], [215, 21], [215, 22], [215, 23], [215, 7], [225, 17], [225, 18], [225, 19], [225, 20], [225, 21], [225, 22], [225, 23], [225, 7]],
  [[236, 17], [236, 18], [236, 19], [236, 20], [236, 21], [236, 22], [236, 23], [236, 7], [237, 17], [237, 18], [237, 19], [237, 20], [237, 21], [237, 22], [237, 23], [237, 7]],
  [[199, 25], [199, 26], [199, 27], [199, 6], [207, 25], [207, 26], [207, 27], [207, 6], [234, 25], [234, 26], [234, 27], [234, 6], [235, 25], [235, 26], [235, 27], [235, 6]],
  [[192, 29], [192, 5], [193, 29], [193, 5], [200, 29], [200, 5], [201, 29], [201, 5], [202, 29], [202, 5], [205, 29], [205, 5], [210, 29], [210, 5], [213, 29], [213, 5]],
  [[218, 29], [218, 5], [219, 29], [219, 5], [238, 29], [238, 5], [240, 29], [240, 5], [242, 29], [242, 5], [243, 29], [243, 5], [255, 29], [255, 5], [203, 0], [204, 0]],
  [[211, 0], [212, 0], [214, 0], [221, 0], [222, 0], [223, 0], [241, 0], [244, 0], [245, 0], [246, 0], [247, 0], [248, 0], [250, 0], [251, 0], [252, 0], [253, 0]],
  [[254, 0], [nil, 206], [nil, 207], [nil, 208], [nil, 209], [nil, 210], [nil, 211], [nil, 212], [nil, 213], [nil, 214], [nil, 215], [nil, 216], [nil, 217], [nil, 218], [nil, 219], [nil, 220]],
  [[1, 17], [1, 18], [1, 19], [1, 20], [1, 21], [1, 22], [1, 23], [1, 7], [135, 17], [135, 18], [135, 19], [135, 20], [135, 21], [135, 22], [135, 23], [135, 7]],
  [[137, 17], [137, 18], [137, 19], [137, 20], [137, 21], [137, 22], [137, 23], [137, 7], [138, 17], [138, 18], [138, 19], [138, 20], [138, 21], [138, 22], [138, 23], [138, 7]],
  [[139, 17], [139, 18], [139, 19], [139, 20], [139, 21], [139, 22], [139, 23], [139, 7], [140, 17], [140, 18], [140, 19], [140, 20], [140, 21], [140, 22], [140, 23], [140, 7]],
  [[141, 17], [141, 18], [141, 19], [141, 20], [141, 21], [141, 22], [141, 23], [141, 7], [143, 17], [143, 18], [143, 19], [143, 20], [143, 21], [143, 22], [143, 23], [143, 7]],
  [[147, 17], [147, 18], [147, 19], [147, 20], [147, 21], [147, 22], [147, 23], [147, 7], [149, 17], [149, 18], [149, 19], [149, 20], [149, 21], [149, 22], [149, 23], [149, 7]],
  [[150, 17], [150, 18], [150, 19], [150, 20], [150, 21], [150, 22], [150, 23], [150, 7], [151, 17], [151, 18], [151, 19], [151, 20], [151, 21], [151, 22], [151, 23], [151, 7]],
  [[152, 17], [152, 18], [152, 19], [152, 20], [152, 21], [152, 22], [152, 23], [152, 7], [155, 17], [155, 18], [155, 19], [155, 20], [155, 21], [155, 22], [155, 23], [155, 7]],
  [[157, 17], [157, 18], [157, 19], [157, 20], [157, 21], [157, 22], [157, 23], [157, 7], [158, 17], [158, 18], [158, 19], [158, 20], [158, 21], [158, 22], [158, 23], [158, 7]],
  [[165, 17], [165, 18], [165, 19], [165, 20], [165, 21], [165, 22], [165, 23], [165, 7], [166, 17], [166, 18], [166, 19], [166, 20], [166, 21], [166, 22], [166, 23], [166, 7]],
  [[168, 17], [168, 18], [168, 19], [168, 20], [168, 21], [168, 22], [168, 23], [168, 7], [174, 17], [174, 18], [174, 19], [174, 20], [174, 21], [174, 22], [174, 23], [174, 7]],
  [[175, 17], [175, 18], [175, 19], [175, 20], [175, 21], [175, 22], [175, 23], [175, 7], [180, 17], [180, 18], [180, 19], [180, 20], [180, 21], [180, 22], [180, 23], [180, 7]],
  [[182, 17], [182, 18], [182, 19], [182, 20], [182, 21], [182, 22], [182, 23], [182, 7], [183, 17], [183, 18], [183, 19], [183, 20], [183, 21], [183, 22], [183, 23], [183, 7]],
  [[188, 17], [188, 18], [188, 19], [188, 20], [188, 21], [188, 22], [188, 23], [188, 7], [191, 17], [191, 18], [191, 19], [191, 20], [191, 21], [191, 22], [191, 23], [191, 7]],
  [[197, 17], [197, 18], [197, 19], [197, 20], [197, 21], [197, 22], [197, 23], [197, 7], [231, 17], [231, 18], [231, 19], [231, 20], [231, 21], [231, 22], [231, 23], [231, 7]],
  [[239, 17], [239, 18], [239, 19], [239, 20], [239, 21], [239, 22], [239, 23], [239, 7], [9, 25], [9, 26], [9, 27], [9, 6], [142, 25], [142, 26], [142, 27], [142, 6]],
  [[144, 25], [144, 26], [144, 27], [144, 6], [145, 25], [145, 26], [145, 27], [145, 6], [148, 25], [148, 26], [148, 27], [148, 6], [159, 25], [159, 26], [159, 27], [159, 6]],
  [[171, 25], [171, 26], [171, 27], [171, 6], [206, 25], [206, 26], [206, 27], [206, 6], [215, 25], [215, 26], [215, 27], [215, 6], [225, 25], [225, 26], [225, 27], [225, 6]],
  [[236, 25], [236, 26], [236, 27], [236, 6], [237, 25], [237, 26], [237, 27], [237, 6], [199, 29], [199, 5], [207, 29], [207, 5], [234, 29], [234, 5], [235, 29], [235, 5]],
  [[192, 0], [193, 0], [200, 0], [201, 0], [202, 0], [205, 0], [210, 0], [213, 0], [218, 0], [219, 0], [238, 0], [240, 0], [242, 0], [243, 0], [255, 0], [nil, 8]],
  [[nil, 222], [nil, 223], [nil, 224], [nil, 225], [nil, 226], [nil, 227], [nil, 228], [nil, 229], [nil, 230], [nil, 231], [nil, 232], [nil, 233], [nil, 234], [nil, 235], [nil, 236], [nil, 237]],
  [[129, 17], [129, 18], [129, 19], [129, 20], [129, 21], [129, 22], [129, 23], [129, 7], [132, 17], [132, 18], [132, 19], [132, 20], [132, 21], [132, 22], [132, 23], [132, 7]],
  [[133, 17], [133, 18], [133, 19], [133, 20], [133, 21], [133, 22], [133, 23], [133, 7], [134, 17], [134, 18], [134, 19], [134, 20], [134, 21], [134, 22], [134, 23], [134, 7]],
  [[136, 17], [136, 18], [136, 19], [136, 20], [136, 21], [136, 22], [136, 23], [136, 7], [146, 17], [146, 18], [146, 19], [146, 20], [146, 21], [146, 22], [146, 23], [146, 7]],
  [[154, 17], [154, 18], [154, 19], [154, 20], [154, 21], [154, 22], [154, 23], [154, 7], [156, 17], [156, 18], [156, 19], [156, 20], [156, 21], [156, 22], [156, 23], [156, 7]],
  [[160, 17], [160, 18], [160, 19], [160, 20], [160, 21], [160, 22], [160, 23], [160, 7], [163, 17], [163, 18], [163, 19], [163, 20], [163, 21], [163, 22], [163, 23], [163, 7]],
  [[164, 17], [164, 18], [164, 19], [164, 20], [164, 21], [164, 22], [164, 23], [164, 7], [169, 17], [169, 18], [169, 19], [169, 20], [169, 21], [169, 22], [169, 23], [169, 7]],
  [[170, 17], [170, 18], [170, 19], [170, 20], [170, 21], [170, 22], [170, 23], [170, 7], [173, 17], [173, 18], [173, 19], [173, 20], [173, 21], [173, 22], [173, 23], [173, 7]],
  [[178, 17], [178, 18], [178, 19], [178, 20], [178, 21], [178, 22], [178, 23], [178, 7], [181, 17], [181, 18], [181, 19], [181, 20], [181, 21], [181, 22], [181, 23], [181, 7]],
  [[185, 17], [185, 18], [185, 19], [185, 20], [185, 21], [185, 22], [185, 23], [185, 7], [186, 17], [186, 18], [186, 19], [186, 20], [186, 21], [186, 22], [186, 23], [186, 7]],
  [[187, 17], [187, 18], [187, 19], [187, 20], [187, 21], [187, 22], [187, 23], [187, 7], [189, 17], [189, 18], [189, 19], [189, 20], [189, 21], [189, 22], [189, 23], [189, 7]],
  [[190, 17], [190, 18], [190, 19], [190, 20], [190, 21], [190, 22], [190, 23], [190, 7], [196, 17], [196, 18], [196, 19], [196, 20], [196, 21], [196, 22], [196, 23], [196, 7]],
  [[198, 17], [198, 18], [198, 19], [198, 20], [198, 21], [198, 22], [198, 23], [198, 7], [228, 17], [228, 18], [228, 19], [228, 20], [228, 21], [228, 22], [228, 23], [228, 7]],
  [[232, 17], [232, 18], [232, 19], [232, 20], [232, 21], [232, 22], [232, 23], [232, 7], [233, 17], [233, 18], [233, 19], [233, 20], [233, 21], [233, 22], [233, 23], [233, 7]],
  [[1, 25], [1, 26], [1, 27], [1, 6], [135, 25], [135, 26], [135, 27], [135, 6], [137, 25], [137, 26], [137, 27], [137, 6], [138, 25], [138, 26], [138, 27], [138, 6]],
  [[139, 25], [139, 26], [139, 27], [139, 6], [140, 25], [140, 26], [140, 27], [140, 6], [141, 25], [141, 26], [141, 27], [141, 6], [143, 25], [143, 26], [143, 27], [143, 6]],
  [[147, 25], [147, 26], [147, 27], [147, 6], [149, 25], [149, 26], [149, 27], [149, 6], [150, 25], [150, 26], [150, 27], [150, 6], [151, 25], [151, 26], [151, 27], [151, 6]],
  [[152, 25], [152, 26], [152, 27], [152, 6], [155, 25], [155, 26], [155, 27], [155, 6], [157, 25], [157, 26], [157, 27], [157, 6], [158, 25], [158, 26], [158, 27], [158, 6]],
  [[165, 25], [165, 26], [165, 27], [165, 6], [166, 25], [166, 26], [166, 27], [166, 6], [168, 25], [168, 26], [168, 27], [168, 6], [174, 25], [174, 26], [174, 27], [174, 6]],
  [[175, 25], [175, 26], [175, 27], [175, 6], [180, 25], [180, 26], [180, 27], [180, 6], [182, 25], [182, 26], [182, 27], [182, 6], [183, 25], [183, 26], [183, 27], [183, 6]],
  [[188, 25], [188, 26], [188, 27], [188, 6], [191, 25], [191, 26], [191, 27], [191, 6], [197, 25], [197, 26], [197, 27], [197, 6], [231, 25], [231, 26], [231, 27], [231, 6]],
  [[239, 25], [239, 26], [239, 27], [239, 6], [9, 29], [9, 5], [142, 29], [142, 5], [144, 29], [144, 5], [145, 29], [145, 5], [148, 29], [148, 5], [159, 29], [159, 5]],
  [[171, 29], [171, 5], [206, 29], [206, 5], [215, 29], [215, 5], [225, 29], [225, 5], [236, 29], [236, 5], [237, 29], [237, 5], [199, 0], [207, 0], [234, 0], [235, 0]],
  [[nil, 238], [nil, 239], [nil, 240], [nil, 241], [nil, 242], [nil, 243], [nil, 244], [nil, 245], [nil, 246], [nil, 247], [nil, 248], [nil, 249], [nil, 250], [nil, 251], [nil, 252], [nil, 253]],
  [[10, 25], [10, 26], [10, 27], [10, 6], [13, 25], [13, 26], [13, 27], [13, 6], [22, 25], [22, 26], [22, 27], [22, 6], [256, 25], [256, 26], [256, 27], [256, 6]],
  [[2, 17], [2, 18], [2, 19], [2, 20], [2, 21], [2, 22], [2, 23], [2, 7], [3, 17], [3, 18], [3, 19], [3, 20], [3, 21], [3, 22], [3, 23], [3, 7]],
  [[4, 17], [4, 18], [4, 19], [4, 20], [4, 21], [4, 22], [4, 23], [4, 7], [5, 17], [5, 18], [5, 19], [5, 20], [5, 21], [5, 22], [5, 23], [5, 7]],
  [[6, 17], [6, 18], [6, 19], [6, 20], [6, 21], [6, 22], [6, 23], [6, 7], [7, 17], [7, 18], [7, 19], [7, 20], [7, 21], [7, 22], [7, 23], [7, 7]],
  [[8, 17], [8, 18], [8, 19], [8, 20], [8, 21], [8, 22], [8, 23], [8, 7], [11, 17], [11, 18], [11, 19], [11, 20], [11, 21], [11, 22], [11, 23], [11, 7]],
  [[12, 17], [12, 18], [12, 19], [12, 20], [12, 21], [12, 22], [12, 23], [12, 7], [14, 17], [14, 18], [14, 19], [14, 20], [14, 21], [14, 22], [14, 23], [14, 7]],
  [[15, 17], [15, 18], [15, 19], [15, 20], [15, 21], [15, 22], [15, 23], [15, 7], [16, 17], [16, 18], [16, 19], [16, 20], [16, 21], [16, 22], [16, 23], [16, 7]],
  [[17, 17], [17, 18], [17, 19], [17, 20], [17, 21], [17, 22], [17, 23], [17, 7], [18, 17], [18, 18], [18, 19], [18, 20], [18, 21], [18, 22], [18, 23], [18, 7]],
  [[19, 17], [19, 18], [19, 19], [19, 20], [19, 21], [19, 22], [19, 23], [19, 7], [20, 17], [20, 18], [20, 19], [20, 20], [20, 21], [20, 22], [20, 23], [20, 7]],
  [[21, 17], [21, 18], [21, 19], [21, 20], [21, 21], [21, 22], [21, 23], [21, 7], [23, 17], [23, 18], [23, 19], [23, 20], [23, 21], [23, 22], [23, 23], [23, 7]],
  [[24, 17], [24, 18], [24, 19], [24, 20], [24, 21], [24, 22], [24, 23], [24, 7], [25, 17], [25, 18], [25, 19], [25, 20], [25, 21], [25, 22], [25, 23], [25, 7]],
  [[26, 17], [26, 18], [26, 19], [26, 20], [26, 21], [26, 22], [26, 23], [26, 7], [27, 17], [27, 18], [27, 19], [27, 20], [27, 21], [27, 22], [27, 23], [27, 7]],
  [[28, 17], [28, 18], [28, 19], [28, 20], [28, 21], [28, 22], [28, 23], [28, 7], [29, 17], [29, 18], [29, 19], [29, 20], [29, 21], [29, 22], [29, 23], [29, 7]],
  [[30, 17], [30, 18], [30, 19], [30, 20], [30, 21], [30, 22], [30, 23], [30, 7], [31, 17], [31, 18], [31, 19], [31, 20], [31, 21], [31, 22], [31, 23], [31, 7]],
  [[127, 17], [127, 18], [127, 19], [127, 20], [127, 21], [127, 22], [127, 23], [127, 7], [220, 17], [220, 18], [220, 19], [220, 20], [220, 21], [220, 22], [220, 23], [220, 7]],
  [[249, 17], [249, 18], [249, 19], [249, 20], [249, 21], [249, 22], [249, 23], [249, 7], [10, 29], [10, 5], [13, 29], [13, 5], [22, 29], [22, 5], [256, 29], [256, 5]],
  [[54, 25], [54, 26], [54, 27], [54, 6], [55, 25], [55, 26], [55, 27], [55, 6], [56, 25], [56, 26], [56, 27], [56, 6], [57, 25], [57, 26], [57, 27], [57, 6]],
  [[211, 17], [211, 18], [211, 19], [211, 20], [211, 21], [211, 22], [211, 23], [211, 7], [212, 17], [212, 18], [212, 19], [212, 20], [212, 21], [212, 22], [212, 23], [212, 7]],
  [[214, 17], [214, 18], [214, 19], [214, 20], [214, 21], [214, 22], [214, 23], [214, 7], [221, 17], [221, 18], [221, 19], [221, 20], [221, 21], [221, 22], [221, 23], [221, 7]],
  [[222, 17], [222, 18], [222, 19], [222, 20], [222, 21], [222, 22], [222, 23], [222, 7], [223, 17], [223, 18], [223, 19], [223, 20], [223, 21], [223, 22], [223, 23], [223, 7]],
  [[241, 17], [241, 18], [241, 19], [241, 20], [241, 21], [241, 22], [241, 23], [241, 7], [244, 17], [244, 18], [244, 19], [244, 20], [244, 21], [244, 22], [244, 23], [244, 7]],
  [[245, 17], [245, 18], [245, 19], [245, 20], [245, 21], [245, 22], [245, 23], [245, 7], [246, 17], [246, 18], [246, 19], [246, 20], [246, 21], [246, 22], [246, 23], [246, 7]],
  [[247, 17], [247, 18], [247, 19], [247, 20], [247, 21], [247, 22], [247, 23], [247, 7], [248, 17], [248, 18], [248, 19], [248, 20], [248, 21], [248, 22], [248, 23], [248, 7]],
  [[250, 17], [250, 18], [250, 19], [250, 20], [250, 21], [250, 22], [250, 23], [250, 7], [251, 17], [251, 18], [251, 19], [251, 20], [251, 21], [251, 22], [251, 23], [251, 7]],
  [[252, 17], [252, 18], [252, 19], [252, 20], [252, 21], [252, 22], [252, 23], [252, 7], [253, 17], [253, 18], [253, 19], [253, 20], [253, 21], [253, 22], [253, 23], [253, 7]],
  [[254, 17], [254, 18], [254, 19], [254, 20], [254, 21], [254, 22], [254, 23], [254, 7], [2, 25], [2, 26], [2, 27], [2, 6], [3, 25], [3, 26], [3, 27], [3, 6]],
  [[4, 25], [4, 26], [4, 27], [4, 6], [5, 25], [5, 26], [5, 27], [5, 6], [6, 25], [6, 26], [6, 27], [6, 6], [7, 25], [7, 26], [7, 27], [7, 6]],
  [[8, 25], [8, 26], [8, 27], [8, 6], [11, 25], [11, 26], [11, 27], [11, 6], [12, 25], [12, 26], [12, 27], [12, 6], [14, 25], [14, 26], [14, 27], [14, 6]],
  [[15, 25], [15, 26], [15, 27], [15, 6], [16, 25], [16, 26], [16, 27], [16, 6], [17, 25], [17, 26], [17, 27], [17, 6], [18, 25], [18, 26], [18, 27], [18, 6]],
  [[19, 25], [19, 26], [19, 27], [19, 6], [20, 25], [20, 26], [20, 27], [20, 6], [21, 25], [21, 26], [21, 27], [21, 6], [23, 25], [23, 26], [23, 27], [23, 6]],
  [[24, 25], [24, 26], [24, 27], [24, 6], [25, 25], [25, 26], [25, 27], [25, 6], [26, 25], [26, 26], [26, 27], [26, 6], [27, 25], [27, 26], [27, 27], [27, 6]],
  [[28, 25], [28, 26], [28, 27], [28, 6], [29, 25], [29, 26], [29, 27], [29, 6], [30, 25], [30, 26], [30, 27], [30, 6], [31, 25], [31, 26], [31, 27], [31, 6]],
  [[127, 25], [127, 26], [127, 27], [127, 6], [220, 25], [220, 26], [220, 27], [220, 6], [249, 25], [249, 26], [249, 27], [249, 6], [10, 0], [13, 0], [22, 0], [256, 0]],
  [[192, 17], [192, 18], [192, 19], [192, 20], [192, 21], [192, 22], [192, 23], [192, 7], [193, 17], [193, 18], [193, 19], [193, 20], [193, 21], [193, 22], [193, 23], [193, 7]],
  [[200, 17], [200, 18], [200, 19], [200, 20], [200, 21], [200, 22], [200, 23], [200, 7], [201, 17], [201, 18], [201, 19], [201, 20], [201, 21], [201, 22], [201, 23], [201, 7]],
  [[202, 17], [202, 18], [202, 19], [202, 20], [202, 21], [202, 22], [202, 23], [202, 7], [205, 17], [205, 18], [205, 19], [205, 20], [205, 21], [205, 22], [205, 23], [205, 7]],
  [[210, 17], [210, 18], [210, 19], [210, 20], [210, 21], [210, 22], [210, 23], [210, 7], [213, 17], [213, 18], [213, 19], [213, 20], [213, 21], [213, 22], [213, 23], [213, 7]],
  [[218, 17], [218, 18], [218, 19], [218, 20], [218, 21], [218, 22], [218, 23], [218, 7], [219, 17], [219, 18], [219, 19], [219, 20], [219, 21], [219, 22], [219, 23], [219, 7]],
  [[238, 17], [238, 18], [238, 19], [238, 20], [238, 21], [238, 22], [238, 23], [238, 7], [240, 17], [240, 18], [240, 19], [240, 20], [240, 21], [240, 22], [240, 23], [240, 7]],
  [[242, 17], [242, 18], [242, 19], [242, 20], [242, 21], [242, 22], [242, 23], [242, 7], [243, 17], [243, 18], [243, 19], [243, 20], [243, 21], [243, 22], [243, 23], [243, 7]],
  [[255, 17], [255, 18], [255, 19], [255, 20], [255, 21], [255, 22], [255, 23], [255, 7], [203, 25], [203, 26], [203, 27], [203, 6], [204, 25], [204, 26], [204, 27], [204, 6]],
  [[211, 25], [211, 26], [211, 27], [211, 6], [212, 25], [212, 26], [212, 27], [212, 6], [214, 25], [214, 26], [214, 27], [214, 6], [221, 25], [221, 26], [221, 27], [221, 6]],
  [[222, 25], [222, 26], [222, 27], [222, 6], [223, 25], [223, 26], [223, 27], [223, 6], [241, 25], [241, 26], [241, 27], [241, 6], [244, 25], [244, 26], [244, 27], [244, 6]],
  [[245, 25], [245, 26], [245, 27], [245, 6], [246, 25], [246, 26], [246, 27], [246, 6], [247, 25], [247, 26], [247, 27], [247, 6], [248, 25], [248, 26], [248, 27], [248, 6]],
  [[250, 25], [250, 26], [250, 27], [250, 6], [251, 25], [251, 26], [251, 27], [251, 6], [252, 25], [252, 26], [252, 27], [252, 6], [253, 25], [253, 26], [253, 27], [253, 6]],
  [[254, 25], [254, 26], [254, 27], [254, 6], [2, 29], [2, 5], [3, 29], [3, 5], [4, 29], [4, 5], [5, 29], [5, 5], [6, 29], [6, 5], [7, 29], [7, 5]],
  [[8, 29], [8, 5], [11, 29], [11, 5], [12, 29], [12, 5], [14, 29], [14, 5], [15, 29], [15, 5], [16, 29], [16, 5], [17, 29], [17, 5], [18, 29], [18, 5]],
  [[19, 29], [19, 5], [20, 29], [20, 5], [21, 29], [21, 5], [23, 29], [23, 5], [24, 29], [24, 5], [25, 29], [25, 5], [26, 29], [26, 5], [27, 29], [27, 5]],
  [[28, 29], [28, 5], [29, 29], [29, 5], [30, 29], [30, 5], [31, 29], [31, 5], [127, 29], [127, 5], [220, 29], [220, 5], [249, 29], [249, 5], [nil, 254], [nil, 255]],
  [[10, 17], [10, 18], [10, 19], [10, 20], [10, 21], [10, 22], [10, 23], [10, 7], [13, 17], [13, 18], [13, 19], [13, 20], [13, 21], [13, 22], [13, 23], [13, 7]],
  [[22, 17], [22, 18], [22, 19], [22, 20], [22, 21], [22, 22], [22, 23], [22, 7], [256, 17], [256, 18], [256, 19], [256, 20], [256, 21], [256, 22], [256, 23], [256, 7]],
].each { |arr| arr.each { |subarr| subarr.each(&:freeze) }.freeze }.freeze

Instance Method Summary collapse

Instance Method Details

#decode(buf) ⇒ String

Decodes provided Huffman coded string.

Parameters:

Returns:

  • (String)

    binary string

Raises:


32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# File 'lib/http/2/huffman.rb', line 32

def decode(buf)
  emit = ''
  state = 0 # start state

  mask = (1 << BITS_AT_ONCE) - 1
  buf.each_byte do |chr|
    (8 / BITS_AT_ONCE - 1).downto(0) do |shift|
      branch = (chr >> (shift * BITS_AT_ONCE)) & mask
      # MACHINE[state] = [final, [transitions]]
      #  [final] unfinished bits so far are prefix of the EOS code.
      # Each transition is [emit, next]
      #  [emit] character to be emitted on this transition, empty string, or EOS.
      #  [next] next state number.
      trans = MACHINE[state][branch]
      fail CompressionError, 'Huffman decode error (EOS found)' if trans.first == EOS
      emit << trans.first.chr if trans.first
      state = trans.last
    end
  end
  # Check whether partial input is correctly filled
  unless state <= MAX_FINAL_STATE
    fail CompressionError, 'Huffman decode error (EOS invalid)'
  end
  emit.force_encoding(Encoding::BINARY)
end

#encode(str) ⇒ String

Encodes provided value via huffman encoding. Length is not encoded in this method.

Parameters:

  • str (String)

Returns:

  • (String)

    binary string


21
22
23
24
25
# File 'lib/http/2/huffman.rb', line 21

def encode(str)
  bitstring = str.each_byte.map { |chr| ENCODE_TABLE[chr] }.join
  bitstring << '1' * ((8 - bitstring.size) % 8)
  [bitstring].pack('B*')
end