xz_lzma2.h 6.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204
  1. /*
  2. * LZMA2 definitions
  3. *
  4. * Authors: Lasse Collin <lasse.collin@tukaani.org>
  5. * Igor Pavlov <https://7-zip.org/>
  6. *
  7. * This file has been put into the public domain.
  8. * You can do whatever you want with this file.
  9. */
  10. #ifndef XZ_LZMA2_H
  11. #define XZ_LZMA2_H
  12. /* Range coder constants */
  13. #define RC_SHIFT_BITS 8
  14. #define RC_TOP_BITS 24
  15. #define RC_TOP_VALUE (1 << RC_TOP_BITS)
  16. #define RC_BIT_MODEL_TOTAL_BITS 11
  17. #define RC_BIT_MODEL_TOTAL (1 << RC_BIT_MODEL_TOTAL_BITS)
  18. #define RC_MOVE_BITS 5
  19. /*
  20. * Maximum number of position states. A position state is the lowest pb
  21. * number of bits of the current uncompressed offset. In some places there
  22. * are different sets of probabilities for different position states.
  23. */
  24. #define POS_STATES_MAX (1 << 4)
  25. /*
  26. * This enum is used to track which LZMA symbols have occurred most recently
  27. * and in which order. This information is used to predict the next symbol.
  28. *
  29. * Symbols:
  30. * - Literal: One 8-bit byte
  31. * - Match: Repeat a chunk of data at some distance
  32. * - Long repeat: Multi-byte match at a recently seen distance
  33. * - Short repeat: One-byte repeat at a recently seen distance
  34. *
  35. * The symbol names are in from STATE_oldest_older_previous. REP means
  36. * either short or long repeated match, and NONLIT means any non-literal.
  37. */
  38. enum lzma_state {
  39. STATE_LIT_LIT,
  40. STATE_MATCH_LIT_LIT,
  41. STATE_REP_LIT_LIT,
  42. STATE_SHORTREP_LIT_LIT,
  43. STATE_MATCH_LIT,
  44. STATE_REP_LIT,
  45. STATE_SHORTREP_LIT,
  46. STATE_LIT_MATCH,
  47. STATE_LIT_LONGREP,
  48. STATE_LIT_SHORTREP,
  49. STATE_NONLIT_MATCH,
  50. STATE_NONLIT_REP
  51. };
  52. /* Total number of states */
  53. #define STATES 12
  54. /* The lowest 7 states indicate that the previous state was a literal. */
  55. #define LIT_STATES 7
  56. /* Indicate that the latest symbol was a literal. */
  57. static inline void lzma_state_literal(enum lzma_state *state)
  58. {
  59. if (*state <= STATE_SHORTREP_LIT_LIT)
  60. *state = STATE_LIT_LIT;
  61. else if (*state <= STATE_LIT_SHORTREP)
  62. *state -= 3;
  63. else
  64. *state -= 6;
  65. }
  66. /* Indicate that the latest symbol was a match. */
  67. static inline void lzma_state_match(enum lzma_state *state)
  68. {
  69. *state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH;
  70. }
  71. /* Indicate that the latest state was a long repeated match. */
  72. static inline void lzma_state_long_rep(enum lzma_state *state)
  73. {
  74. *state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP;
  75. }
  76. /* Indicate that the latest symbol was a short match. */
  77. static inline void lzma_state_short_rep(enum lzma_state *state)
  78. {
  79. *state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP;
  80. }
  81. /* Test if the previous symbol was a literal. */
  82. static inline bool lzma_state_is_literal(enum lzma_state state)
  83. {
  84. return state < LIT_STATES;
  85. }
  86. /* Each literal coder is divided in three sections:
  87. * - 0x001-0x0FF: Without match byte
  88. * - 0x101-0x1FF: With match byte; match bit is 0
  89. * - 0x201-0x2FF: With match byte; match bit is 1
  90. *
  91. * Match byte is used when the previous LZMA symbol was something else than
  92. * a literal (that is, it was some kind of match).
  93. */
  94. #define LITERAL_CODER_SIZE 0x300
  95. /* Maximum number of literal coders */
  96. #define LITERAL_CODERS_MAX (1 << 4)
  97. /* Minimum length of a match is two bytes. */
  98. #define MATCH_LEN_MIN 2
  99. /* Match length is encoded with 4, 5, or 10 bits.
  100. *
  101. * Length Bits
  102. * 2-9 4 = Choice=0 + 3 bits
  103. * 10-17 5 = Choice=1 + Choice2=0 + 3 bits
  104. * 18-273 10 = Choice=1 + Choice2=1 + 8 bits
  105. */
  106. #define LEN_LOW_BITS 3
  107. #define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)
  108. #define LEN_MID_BITS 3
  109. #define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)
  110. #define LEN_HIGH_BITS 8
  111. #define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS)
  112. #define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS)
  113. /*
  114. * Maximum length of a match is 273 which is a result of the encoding
  115. * described above.
  116. */
  117. #define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1)
  118. /*
  119. * Different sets of probabilities are used for match distances that have
  120. * very short match length: Lengths of 2, 3, and 4 bytes have a separate
  121. * set of probabilities for each length. The matches with longer length
  122. * use a shared set of probabilities.
  123. */
  124. #define DIST_STATES 4
  125. /*
  126. * Get the index of the appropriate probability array for decoding
  127. * the distance slot.
  128. */
  129. static inline uint32_t lzma_get_dist_state(uint32_t len)
  130. {
  131. return len < DIST_STATES + MATCH_LEN_MIN
  132. ? len - MATCH_LEN_MIN : DIST_STATES - 1;
  133. }
  134. /*
  135. * The highest two bits of a 32-bit match distance are encoded using six bits.
  136. * This six-bit value is called a distance slot. This way encoding a 32-bit
  137. * value takes 6-36 bits, larger values taking more bits.
  138. */
  139. #define DIST_SLOT_BITS 6
  140. #define DIST_SLOTS (1 << DIST_SLOT_BITS)
  141. /* Match distances up to 127 are fully encoded using probabilities. Since
  142. * the highest two bits (distance slot) are always encoded using six bits,
  143. * the distances 0-3 don't need any additional bits to encode, since the
  144. * distance slot itself is the same as the actual distance. DIST_MODEL_START
  145. * indicates the first distance slot where at least one additional bit is
  146. * needed.
  147. */
  148. #define DIST_MODEL_START 4
  149. /*
  150. * Match distances greater than 127 are encoded in three pieces:
  151. * - distance slot: the highest two bits
  152. * - direct bits: 2-26 bits below the highest two bits
  153. * - alignment bits: four lowest bits
  154. *
  155. * Direct bits don't use any probabilities.
  156. *
  157. * The distance slot value of 14 is for distances 128-191.
  158. */
  159. #define DIST_MODEL_END 14
  160. /* Distance slots that indicate a distance <= 127. */
  161. #define FULL_DISTANCES_BITS (DIST_MODEL_END / 2)
  162. #define FULL_DISTANCES (1 << FULL_DISTANCES_BITS)
  163. /*
  164. * For match distances greater than 127, only the highest two bits and the
  165. * lowest four bits (alignment) is encoded using probabilities.
  166. */
  167. #define ALIGN_BITS 4
  168. #define ALIGN_SIZE (1 << ALIGN_BITS)
  169. #define ALIGN_MASK (ALIGN_SIZE - 1)
  170. /* Total number of all probability variables */
  171. #define PROBS_TOTAL (1846 + LITERAL_CODERS_MAX * LITERAL_CODER_SIZE)
  172. /*
  173. * LZMA remembers the four most recent match distances. Reusing these
  174. * distances tends to take less space than re-encoding the actual
  175. * distance value.
  176. */
  177. #define REPS 4
  178. #endif