ggstd/compress/flate/
token.rs

1// Copyright 2023 The rust-ggstd authors. All rights reserved.
2// Copyright 2009 The Go Authors. All rights reserved.
3// Use of this source code is governed by a BSD-style
4// license that can be found in the LICENSE file.
5
6// 2 bits:   type   0 = literal  1=EOF  2=Match   3=Unused
7// 8 bits:   xlength = length - MIN_MATCH_LENGTH
8// 22 bits   xoffset = offset - MIN_OFFSET_SIZE, or literal
9const LENGTH_SHIFT: u32 = 22;
10const OFFSET_MASK: u32 = (1 << LENGTH_SHIFT) - 1;
11// const TYPE_MASK: u32 = 3 << 30;
12const LITERAL_TYPE: u32 = 0 << 30;
13pub(super) const MATCH_TYPE: u32 = 1 << 30;
14
15// The length code for length X (MIN_MATCH_LENGTH <= X <= MAX_MATCH_LENGTH)
16// is lengthCodes[length - MIN_MATCH_LENGTH]
17const LENGTH_CODES: &[u32] = &[
18    0, 1, 2, 3, 4, 5, 6, 7, 8, 8, //
19    9, 9, 10, 10, 11, 11, 12, 12, 12, 12, //
20    13, 13, 13, 13, 14, 14, 14, 14, 15, 15, //
21    15, 15, 16, 16, 16, 16, 16, 16, 16, 16, //
22    17, 17, 17, 17, 17, 17, 17, 17, 18, 18, //
23    18, 18, 18, 18, 18, 18, 19, 19, 19, 19, //
24    19, 19, 19, 19, 20, 20, 20, 20, 20, 20, //
25    20, 20, 20, 20, 20, 20, 20, 20, 20, 20, //
26    21, 21, 21, 21, 21, 21, 21, 21, 21, 21, //
27    21, 21, 21, 21, 21, 21, 22, 22, 22, 22, //
28    22, 22, 22, 22, 22, 22, 22, 22, 22, 22, //
29    22, 22, 23, 23, 23, 23, 23, 23, 23, 23, //
30    23, 23, 23, 23, 23, 23, 23, 23, 24, 24, //
31    24, 24, 24, 24, 24, 24, 24, 24, 24, 24, //
32    24, 24, 24, 24, 24, 24, 24, 24, 24, 24, //
33    24, 24, 24, 24, 24, 24, 24, 24, 24, 24, //
34    25, 25, 25, 25, 25, 25, 25, 25, 25, 25, //
35    25, 25, 25, 25, 25, 25, 25, 25, 25, 25, //
36    25, 25, 25, 25, 25, 25, 25, 25, 25, 25, //
37    25, 25, 26, 26, 26, 26, 26, 26, 26, 26, //
38    26, 26, 26, 26, 26, 26, 26, 26, 26, 26, //
39    26, 26, 26, 26, 26, 26, 26, 26, 26, 26, //
40    26, 26, 26, 26, 27, 27, 27, 27, 27, 27, //
41    27, 27, 27, 27, 27, 27, 27, 27, 27, 27, //
42    27, 27, 27, 27, 27, 27, 27, 27, 27, 27, //
43    27, 27, 27, 27, 27, 28, //
44];
45
46const OFFSET_CODES: &[u32] = &[
47    0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, //
48    8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, //
49    10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, //
50    11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, //
51    12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, //
52    12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, //
53    13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, //
54    13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, //
55    14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, //
56    14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, //
57    14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, //
58    14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, //
59    15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, //
60    15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, //
61    15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, //
62    15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, //
63];
64
65pub(super) type Token = u32;
66
67/// Convert a literal into a literal token.
68pub(super) fn literal_token(literal: u32) -> Token {
69    (LITERAL_TYPE + literal) as Token
70}
71
72/// Convert a < xlength, xoffset > pair into a match token.
73pub(super) fn match_token(xlength: u32, xoffset: u32) -> Token {
74    (MATCH_TYPE + (xlength << LENGTH_SHIFT) + xoffset) as Token
75}
76
77pub(super) trait TokenTrait {
78    fn literal(&self) -> u32;
79    fn offset(&self) -> u32;
80    fn length(&self) -> u32;
81}
82
83impl TokenTrait for Token {
84    /// Returns the literal of a literal token.
85    fn literal(&self) -> u32 {
86        self - LITERAL_TYPE
87    }
88
89    /// Returns the extra offset of a match token.
90    fn offset(&self) -> u32 {
91        self & OFFSET_MASK
92    }
93
94    fn length(&self) -> u32 {
95        (self - MATCH_TYPE) >> LENGTH_SHIFT
96    }
97}
98
99pub(super) fn length_code(len: u32) -> usize {
100    LENGTH_CODES[len as usize] as usize
101}
102
103// Returns the offset code corresponding to a specific offset.
104pub(super) fn offset_code(off: usize) -> usize {
105    if off < OFFSET_CODES.len() {
106        return OFFSET_CODES[off] as usize;
107    }
108    if off >> 7 < OFFSET_CODES.len() {
109        return (OFFSET_CODES[off >> 7] + 14) as usize;
110    }
111    (OFFSET_CODES[off >> 14] + 28) as usize
112}
ggstd/compress/flate/token.rs

ggstd/compress/flate/
token.rs
