FastEncoderStatus.cs 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245
  1. // Licensed to the .NET Foundation under one or more agreements.
  2. // The .NET Foundation licenses this file to you under the MIT license.
  3. // See the LICENSE file in the project root for more information.
  4. using System.Diagnostics;
  5. namespace SharpCompress.Compressors.Deflate64
  6. {
  7. internal static class FastEncoderStatics
  8. {
  9. // static information for encoding, DO NOT MODIFY
  10. internal static readonly byte[] FAST_ENCODER_TREE_STRUCTURE_DATA =
  11. {
  12. 0xec,0xbd,0x07,0x60,0x1c,0x49,0x96,0x25,0x26,0x2f,0x6d,0xca,
  13. 0x7b,0x7f,0x4a,0xf5,0x4a,0xd7,0xe0,0x74,0xa1,0x08,0x80,0x60,
  14. 0x13,0x24,0xd8,0x90,0x40,0x10,0xec,0xc1,0x88,0xcd,0xe6,0x92,
  15. 0xec,0x1d,0x69,0x47,0x23,0x29,0xab,0x2a,0x81,0xca,0x65,0x56,
  16. 0x65,0x5d,0x66,0x16,0x40,0xcc,0xed,0x9d,0xbc,0xf7,0xde,0x7b,
  17. 0xef,0xbd,0xf7,0xde,0x7b,0xef,0xbd,0xf7,0xba,0x3b,0x9d,0x4e,
  18. 0x27,0xf7,0xdf,0xff,0x3f,0x5c,0x66,0x64,0x01,0x6c,0xf6,0xce,
  19. 0x4a,0xda,0xc9,0x9e,0x21,0x80,0xaa,0xc8,0x1f,0x3f,0x7e,0x7c,
  20. 0x1f,0x3f
  21. };
  22. internal static readonly byte[] B_FINAL_FAST_ENCODER_TREE_STRUCTURE_DATA =
  23. {
  24. 0xed,0xbd,0x07,0x60,0x1c,0x49,0x96,0x25,0x26,0x2f,0x6d,0xca,
  25. 0x7b,0x7f,0x4a,0xf5,0x4a,0xd7,0xe0,0x74,0xa1,0x08,0x80,0x60,
  26. 0x13,0x24,0xd8,0x90,0x40,0x10,0xec,0xc1,0x88,0xcd,0xe6,0x92,
  27. 0xec,0x1d,0x69,0x47,0x23,0x29,0xab,0x2a,0x81,0xca,0x65,0x56,
  28. 0x65,0x5d,0x66,0x16,0x40,0xcc,0xed,0x9d,0xbc,0xf7,0xde,0x7b,
  29. 0xef,0xbd,0xf7,0xde,0x7b,0xef,0xbd,0xf7,0xba,0x3b,0x9d,0x4e,
  30. 0x27,0xf7,0xdf,0xff,0x3f,0x5c,0x66,0x64,0x01,0x6c,0xf6,0xce,
  31. 0x4a,0xda,0xc9,0x9e,0x21,0x80,0xaa,0xc8,0x1f,0x3f,0x7e,0x7c,
  32. 0x1f,0x3f
  33. };
  34. // Output a currentMatch with length matchLen (>= MIN_MATCH) and displacement matchPos
  35. //
  36. // Optimisation: unlike the other encoders, here we have an array of codes for each currentMatch
  37. // length (not just each currentMatch length slot), complete with all the extra bits filled in, in
  38. // a single array element.
  39. //
  40. // There are many advantages to doing this:
  41. //
  42. // 1. A single array lookup on g_FastEncoderLiteralCodeInfo, instead of separate array lookups
  43. // on g_LengthLookup (to get the length slot), g_FastEncoderLiteralTreeLength,
  44. // g_FastEncoderLiteralTreeCode, g_ExtraLengthBits, and g_BitMask
  45. //
  46. // 2. The array is an array of ULONGs, so no access penalty, unlike for accessing those USHORT
  47. // code arrays in the other encoders (although they could be made into ULONGs with some
  48. // modifications to the source).
  49. //
  50. // Note, if we could guarantee that codeLen <= 16 always, then we could skip an if statement here.
  51. //
  52. // A completely different optimisation is used for the distance codes since, obviously, a table for
  53. // all 8192 distances combining their extra bits is not feasible. The distance codeinfo table is
  54. // made up of code[], len[] and # extraBits for this code.
  55. //
  56. // The advantages are similar to the above; a ULONG array instead of a USHORT and BYTE array, better
  57. // cache locality, fewer memory operations.
  58. //
  59. // Encoding information for literal and Length.
  60. // The least 5 significant bits are the length
  61. // and the rest is the code bits.
  62. internal static readonly uint[] FAST_ENCODER_LITERAL_CODE_INFO =
  63. {
  64. 0x0000d7ee,0x0004d7ee,0x0002d7ee,0x0006d7ee,0x0001d7ee,0x0005d7ee,0x0003d7ee,
  65. 0x0007d7ee,0x000037ee,0x0000c7ec,0x00000126,0x000437ee,0x000237ee,0x000637ee,
  66. 0x000137ee,0x000537ee,0x000337ee,0x000737ee,0x0000b7ee,0x0004b7ee,0x0002b7ee,
  67. 0x0006b7ee,0x0001b7ee,0x0005b7ee,0x0003b7ee,0x0007b7ee,0x000077ee,0x000477ee,
  68. 0x000277ee,0x000677ee,0x000017ed,0x000177ee,0x00000526,0x000577ee,0x000023ea,
  69. 0x0001c7ec,0x000377ee,0x000777ee,0x000217ed,0x000063ea,0x00000b68,0x00000ee9,
  70. 0x00005beb,0x000013ea,0x00000467,0x00001b68,0x00000c67,0x00002ee9,0x00000768,
  71. 0x00001768,0x00000f68,0x00001ee9,0x00001f68,0x00003ee9,0x000053ea,0x000001e9,
  72. 0x000000e8,0x000021e9,0x000011e9,0x000010e8,0x000031e9,0x000033ea,0x000008e8,
  73. 0x0000f7ee,0x0004f7ee,0x000018e8,0x000009e9,0x000004e8,0x000029e9,0x000014e8,
  74. 0x000019e9,0x000073ea,0x0000dbeb,0x00000ce8,0x00003beb,0x0002f7ee,0x000039e9,
  75. 0x00000bea,0x000005e9,0x00004bea,0x000025e9,0x000027ec,0x000015e9,0x000035e9,
  76. 0x00000de9,0x00002bea,0x000127ec,0x0000bbeb,0x0006f7ee,0x0001f7ee,0x0000a7ec,
  77. 0x00007beb,0x0005f7ee,0x0000fbeb,0x0003f7ee,0x0007f7ee,0x00000fee,0x00000326,
  78. 0x00000267,0x00000a67,0x00000667,0x00000726,0x00001ce8,0x000002e8,0x00000e67,
  79. 0x000000a6,0x0001a7ec,0x00002de9,0x000004a6,0x00000167,0x00000967,0x000002a6,
  80. 0x00000567,0x000117ed,0x000006a6,0x000001a6,0x000005a6,0x00000d67,0x000012e8,
  81. 0x00000ae8,0x00001de9,0x00001ae8,0x000007eb,0x000317ed,0x000067ec,0x000097ed,
  82. 0x000297ed,0x00040fee,0x00020fee,0x00060fee,0x00010fee,0x00050fee,0x00030fee,
  83. 0x00070fee,0x00008fee,0x00048fee,0x00028fee,0x00068fee,0x00018fee,0x00058fee,
  84. 0x00038fee,0x00078fee,0x00004fee,0x00044fee,0x00024fee,0x00064fee,0x00014fee,
  85. 0x00054fee,0x00034fee,0x00074fee,0x0000cfee,0x0004cfee,0x0002cfee,0x0006cfee,
  86. 0x0001cfee,0x0005cfee,0x0003cfee,0x0007cfee,0x00002fee,0x00042fee,0x00022fee,
  87. 0x00062fee,0x00012fee,0x00052fee,0x00032fee,0x00072fee,0x0000afee,0x0004afee,
  88. 0x0002afee,0x0006afee,0x0001afee,0x0005afee,0x0003afee,0x0007afee,0x00006fee,
  89. 0x00046fee,0x00026fee,0x00066fee,0x00016fee,0x00056fee,0x00036fee,0x00076fee,
  90. 0x0000efee,0x0004efee,0x0002efee,0x0006efee,0x0001efee,0x0005efee,0x0003efee,
  91. 0x0007efee,0x00001fee,0x00041fee,0x00021fee,0x00061fee,0x00011fee,0x00051fee,
  92. 0x00031fee,0x00071fee,0x00009fee,0x00049fee,0x00029fee,0x00069fee,0x00019fee,
  93. 0x00059fee,0x00039fee,0x00079fee,0x00005fee,0x00045fee,0x00025fee,0x00065fee,
  94. 0x00015fee,0x00055fee,0x00035fee,0x00075fee,0x0000dfee,0x0004dfee,0x0002dfee,
  95. 0x0006dfee,0x0001dfee,0x0005dfee,0x0003dfee,0x0007dfee,0x00003fee,0x00043fee,
  96. 0x00023fee,0x00063fee,0x00013fee,0x00053fee,0x00033fee,0x00073fee,0x0000bfee,
  97. 0x0004bfee,0x0002bfee,0x0006bfee,0x0001bfee,0x0005bfee,0x0003bfee,0x0007bfee,
  98. 0x00007fee,0x00047fee,0x00027fee,0x00067fee,0x00017fee,0x000197ed,0x000397ed,
  99. 0x000057ed,0x00057fee,0x000257ed,0x00037fee,0x000157ed,0x00077fee,0x000357ed,
  100. 0x0000ffee,0x0004ffee,0x0002ffee,0x0006ffee,0x0001ffee,0x00000084,0x00000003,
  101. 0x00000184,0x00000044,0x00000144,0x000000c5,0x000002c5,0x000001c5,0x000003c6,
  102. 0x000007c6,0x00000026,0x00000426,0x000003a7,0x00000ba7,0x000007a7,0x00000fa7,
  103. 0x00000227,0x00000627,0x00000a27,0x00000e27,0x00000068,0x00000868,0x00001068,
  104. 0x00001868,0x00000369,0x00001369,0x00002369,0x00003369,0x000006ea,0x000026ea,
  105. 0x000046ea,0x000066ea,0x000016eb,0x000036eb,0x000056eb,0x000076eb,0x000096eb,
  106. 0x0000b6eb,0x0000d6eb,0x0000f6eb,0x00003dec,0x00007dec,0x0000bdec,0x0000fdec,
  107. 0x00013dec,0x00017dec,0x0001bdec,0x0001fdec,0x00006bed,0x0000ebed,0x00016bed,
  108. 0x0001ebed,0x00026bed,0x0002ebed,0x00036bed,0x0003ebed,0x000003ec,0x000043ec,
  109. 0x000083ec,0x0000c3ec,0x000103ec,0x000143ec,0x000183ec,0x0001c3ec,0x00001bee,
  110. 0x00009bee,0x00011bee,0x00019bee,0x00021bee,0x00029bee,0x00031bee,0x00039bee,
  111. 0x00041bee,0x00049bee,0x00051bee,0x00059bee,0x00061bee,0x00069bee,0x00071bee,
  112. 0x00079bee,0x000167f0,0x000367f0,0x000567f0,0x000767f0,0x000967f0,0x000b67f0,
  113. 0x000d67f0,0x000f67f0,0x001167f0,0x001367f0,0x001567f0,0x001767f0,0x001967f0,
  114. 0x001b67f0,0x001d67f0,0x001f67f0,0x000087ef,0x000187ef,0x000287ef,0x000387ef,
  115. 0x000487ef,0x000587ef,0x000687ef,0x000787ef,0x000887ef,0x000987ef,0x000a87ef,
  116. 0x000b87ef,0x000c87ef,0x000d87ef,0x000e87ef,0x000f87ef,0x0000e7f0,0x0002e7f0,
  117. 0x0004e7f0,0x0006e7f0,0x0008e7f0,0x000ae7f0,0x000ce7f0,0x000ee7f0,0x0010e7f0,
  118. 0x0012e7f0,0x0014e7f0,0x0016e7f0,0x0018e7f0,0x001ae7f0,0x001ce7f0,0x001ee7f0,
  119. 0x0005fff3,0x000dfff3,0x0015fff3,0x001dfff3,0x0025fff3,0x002dfff3,0x0035fff3,
  120. 0x003dfff3,0x0045fff3,0x004dfff3,0x0055fff3,0x005dfff3,0x0065fff3,0x006dfff3,
  121. 0x0075fff3,0x007dfff3,0x0085fff3,0x008dfff3,0x0095fff3,0x009dfff3,0x00a5fff3,
  122. 0x00adfff3,0x00b5fff3,0x00bdfff3,0x00c5fff3,0x00cdfff3,0x00d5fff3,0x00ddfff3,
  123. 0x00e5fff3,0x00edfff3,0x00f5fff3,0x00fdfff3,0x0003fff3,0x000bfff3,0x0013fff3,
  124. 0x001bfff3,0x0023fff3,0x002bfff3,0x0033fff3,0x003bfff3,0x0043fff3,0x004bfff3,
  125. 0x0053fff3,0x005bfff3,0x0063fff3,0x006bfff3,0x0073fff3,0x007bfff3,0x0083fff3,
  126. 0x008bfff3,0x0093fff3,0x009bfff3,0x00a3fff3,0x00abfff3,0x00b3fff3,0x00bbfff3,
  127. 0x00c3fff3,0x00cbfff3,0x00d3fff3,0x00dbfff3,0x00e3fff3,0x00ebfff3,0x00f3fff3,
  128. 0x00fbfff3,0x0007fff3,0x000ffff3,0x0017fff3,0x001ffff3,0x0027fff3,0x002ffff3,
  129. 0x0037fff3,0x003ffff3,0x0047fff3,0x004ffff3,0x0057fff3,0x005ffff3,0x0067fff3,
  130. 0x006ffff3,0x0077fff3,0x007ffff3,0x0087fff3,0x008ffff3,0x0097fff3,0x009ffff3,
  131. 0x00a7fff3,0x00affff3,0x00b7fff3,0x00bffff3,0x00c7fff3,0x00cffff3,0x00d7fff3,
  132. 0x00dffff3,0x00e7fff3,0x00effff3,0x00f7fff3,0x00fffff3,0x0001e7f1,0x0003e7f1,
  133. 0x0005e7f1,0x0007e7f1,0x0009e7f1,0x000be7f1,0x000de7f1,0x000fe7f1,0x0011e7f1,
  134. 0x0013e7f1,0x0015e7f1,0x0017e7f1,0x0019e7f1,0x001be7f1,0x001de7f1,0x001fe7f1,
  135. 0x0021e7f1,0x0023e7f1,0x0025e7f1,0x0027e7f1,0x0029e7f1,0x002be7f1,0x002de7f1,
  136. 0x002fe7f1,0x0031e7f1,0x0033e7f1,0x0035e7f1,0x0037e7f1,0x0039e7f1,0x003be7f1,
  137. 0x003de7f1,0x000047eb
  138. };
  139. internal static readonly uint[] FAST_ENCODER_DISTANCE_CODE_INFO =
  140. {
  141. 0x00000f06,0x0001ff0a,0x0003ff0b,0x0007ff0b,0x0000ff19,0x00003f18,0x0000bf28,
  142. 0x00007f28,0x00001f37,0x00005f37,0x00000d45,0x00002f46,0x00000054,0x00001d55,
  143. 0x00000864,0x00000365,0x00000474,0x00001375,0x00000c84,0x00000284,0x00000a94,
  144. 0x00000694,0x00000ea4,0x000001a4,0x000009b4,0x00000bb5,0x000005c4,0x00001bc5,
  145. 0x000007d5,0x000017d5,0x00000000,0x00000100
  146. };
  147. internal static readonly uint[] BIT_MASK = { 0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767 };
  148. internal static readonly byte[] EXTRA_LENGTH_BITS = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 };
  149. internal static readonly byte[] EXTRA_DISTANCE_BITS = { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 0, 0 };
  150. internal const int NUM_CHARS = 256;
  151. internal const int NUM_LENGTH_BASE_CODES = 29;
  152. internal const int NUM_DIST_BASE_CODES = 30;
  153. internal const uint FAST_ENCODER_POST_TREE_BIT_BUF = 0x0022;
  154. internal const int FAST_ENCODER_POST_TREE_BIT_COUNT = 9;
  155. internal const uint NO_COMPRESSION_HEADER = 0x0;
  156. internal const int NO_COMPRESSION_HEADER_BIT_COUNT = 3;
  157. internal const uint B_FINAL_NO_COMPRESSION_HEADER = 0x1;
  158. internal const int B_FINAL_NO_COMPRESSION_HEADER_BIT_COUNT = 3;
  159. internal const int MAX_CODE_LEN = 16;
  160. private static readonly byte[] S_DIST_LOOKUP = CreateDistanceLookup();
  161. private static byte[] CreateDistanceLookup()
  162. {
  163. byte[] result = new byte[512];
  164. // Generate the global slot tables which allow us to convert a distance
  165. // (0..32K) to a distance slot (0..29)
  166. //
  167. // Distance table
  168. // Extra Extra Extra
  169. // Code Bits Dist Code Bits Dist Code Bits Distance
  170. // ---- ---- ---- ---- ---- ------ ---- ---- --------
  171. // 0 0 1 10 4 33-48 20 9 1025-1536
  172. // 1 0 2 11 4 49-64 21 9 1537-2048
  173. // 2 0 3 12 5 65-96 22 10 2049-3072
  174. // 3 0 4 13 5 97-128 23 10 3073-4096
  175. // 4 1 5,6 14 6 129-192 24 11 4097-6144
  176. // 5 1 7,8 15 6 193-256 25 11 6145-8192
  177. // 6 2 9-12 16 7 257-384 26 12 8193-12288
  178. // 7 2 13-16 17 7 385-512 27 12 12289-16384
  179. // 8 3 17-24 18 8 513-768 28 13 16385-24576
  180. // 9 3 25-32 19 8 769-1024 29 13 24577-32768
  181. // Initialize the mapping length (0..255) -> length code (0..28)
  182. //int length = 0;
  183. //for (code = 0; code < FastEncoderStatics.NumLengthBaseCodes-1; code++) {
  184. // for (int n = 0; n < (1 << FastEncoderStatics.ExtraLengthBits[code]); n++)
  185. // lengthLookup[length++] = (byte) code;
  186. //}
  187. //lengthLookup[length-1] = (byte) code;
  188. // Initialize the mapping dist (0..32K) -> dist code (0..29)
  189. int dist = 0;
  190. int code;
  191. for (code = 0; code < 16; code++)
  192. {
  193. for (int n = 0; n < (1 << EXTRA_DISTANCE_BITS[code]); n++)
  194. result[dist++] = (byte)code;
  195. }
  196. dist >>= 7; // from now on, all distances are divided by 128
  197. for (; code < NUM_DIST_BASE_CODES; code++)
  198. {
  199. for (int n = 0; n < (1 << (EXTRA_DISTANCE_BITS[code] - 7)); n++)
  200. result[256 + dist++] = (byte)code;
  201. }
  202. return result;
  203. }
  204. // Return the position slot (0...29) of a match offset (0...32767)
  205. internal static int GetSlot(int pos) =>
  206. S_DIST_LOOKUP[((pos) < 256) ? (pos) : (256 + ((pos) >> 7))];
  207. // Reverse 'length' of the bits in code
  208. public static uint BitReverse(uint code, int length)
  209. {
  210. uint newCode = 0;
  211. Debug.Assert(length > 0 && length <= 16, "Invalid len");
  212. do
  213. {
  214. newCode |= (code & 1);
  215. newCode <<= 1;
  216. code >>= 1;
  217. } while (--length > 0);
  218. return newCode >> 1;
  219. }
  220. }
  221. }