1 // Copyright (C) 2019, Cloudflare, Inc.
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
6 // met:
7 //
8 // * Redistributions of source code must retain the above copyright notice,
9 // this list of conditions and the following disclaimer.
10 //
11 // * Redistributions in binary form must reproduce the above copyright
12 // notice, this list of conditions and the following disclaimer in the
13 // documentation and/or other materials provided with the distribution.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
16 // IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
17 // THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
18 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
19 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27 use super::Error;
28 use super::Result;
29
30 use self::table::DECODE_TABLE;
31 use self::table::ENCODE_TABLE;
32
decode(b: &mut octets::Octets) -> Result<Vec<u8>>33 pub fn decode(b: &mut octets::Octets) -> Result<Vec<u8>> {
34 // Max compression ratio is >= 0.5
35 let mut out = Vec::with_capacity(b.len() << 1);
36
37 let mut decoder = Decoder::new();
38
39 while b.cap() > 0 {
40 let byte = b.get_u8()?;
41
42 if let Some(b) = decoder.decode4(byte >> 4)? {
43 out.push(b);
44 }
45
46 if let Some(b) = decoder.decode4(byte & 0xf)? {
47 out.push(b);
48 }
49 }
50
51 if !decoder.is_final() {
52 return Err(Error::InvalidHuffmanEncoding);
53 }
54
55 Ok(out)
56 }
57
encode(src: &[u8], out: &mut octets::OctetsMut, low: bool) -> Result<()>58 pub fn encode(src: &[u8], out: &mut octets::OctetsMut, low: bool) -> Result<()> {
59 let mut bits: u64 = 0;
60 let mut bits_left = 40;
61
62 for &b in src {
63 let b = if low { b.to_ascii_lowercase() } else { b };
64
65 let (nbits, code) = ENCODE_TABLE[b as usize];
66
67 bits |= code << (bits_left - nbits);
68 bits_left -= nbits;
69
70 while bits_left <= 32 {
71 out.put_u8((bits >> 32) as u8)?;
72
73 bits <<= 8;
74 bits_left += 8;
75 }
76 }
77
78 if bits_left != 40 {
79 // This writes the EOS token
80 bits |= (1 << bits_left) - 1;
81
82 out.put_u8((bits >> 32) as u8)?;
83 }
84
85 Ok(())
86 }
87
encode_output_length(src: &[u8], low: bool) -> Result<usize>88 pub fn encode_output_length(src: &[u8], low: bool) -> Result<usize> {
89 let mut bits: usize = 0;
90
91 for &b in src {
92 let b = if low { b.to_ascii_lowercase() } else { b };
93
94 let (nbits, _) = ENCODE_TABLE[b as usize];
95 bits += nbits;
96 }
97
98 let mut len = bits / 8;
99
100 if bits & 7 != 0 {
101 len += 1;
102 }
103
104 if len > src.len() {
105 return Err(Error::InflatedHuffmanEncoding);
106 }
107
108 Ok(len)
109 }
110
111 struct Decoder {
112 state: usize,
113 maybe_eos: bool,
114 }
115
116 impl Decoder {
new() -> Decoder117 fn new() -> Decoder {
118 Decoder {
119 state: 0,
120 maybe_eos: false,
121 }
122 }
123
124 // Decodes 4 bits
decode4(&mut self, input: u8) -> Result<Option<u8>>125 fn decode4(&mut self, input: u8) -> Result<Option<u8>> {
126 const MAYBE_EOS: u8 = 1;
127 const DECODED: u8 = 2;
128 const ERROR: u8 = 4;
129
130 // (next-state, byte, flags)
131 let (next, byte, flags) = DECODE_TABLE[self.state][input as usize];
132
133 if flags & ERROR == ERROR {
134 // Data followed the EOS marker
135 return Err(Error::InvalidHuffmanEncoding);
136 }
137
138 let ret = if flags & DECODED == DECODED {
139 Some(byte)
140 } else {
141 None
142 };
143
144 self.state = next;
145 self.maybe_eos = flags & MAYBE_EOS == MAYBE_EOS;
146
147 Ok(ret)
148 }
149
is_final(&self) -> bool150 fn is_final(&self) -> bool {
151 self.state == 0 || self.maybe_eos
152 }
153 }
154
155 mod table;
156