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 crate::octets;
28
29 use super::Error;
30 use super::Result;
31
32 use self::table::DECODE_TABLE;
33 use self::table::ENCODE_TABLE;
34
decode(b: &mut octets::Octets) -> Result<Vec<u8>>35 pub fn decode(b: &mut octets::Octets) -> Result<Vec<u8>> {
36 // Max compression ratio is >= 0.5
37 let mut out = Vec::with_capacity(b.len() << 1);
38
39 let mut decoder = Decoder::new();
40
41 while b.cap() > 0 {
42 let byte = b.get_u8()?;
43
44 if let Some(b) = decoder.decode4(byte >> 4)? {
45 out.push(b);
46 }
47
48 if let Some(b) = decoder.decode4(byte & 0xf)? {
49 out.push(b);
50 }
51 }
52
53 if !decoder.is_final() {
54 return Err(Error::InvalidHuffmanEncoding);
55 }
56
57 Ok(out)
58 }
59
encode(src: &[u8], out: &mut octets::OctetsMut, low: bool) -> Result<()>60 pub fn encode(src: &[u8], out: &mut octets::OctetsMut, low: bool) -> Result<()> {
61 let mut bits: u64 = 0;
62 let mut bits_left = 40;
63
64 for &b in src {
65 let b = if low { b.to_ascii_lowercase() } else { b };
66
67 let (nbits, code) = ENCODE_TABLE[b as usize];
68
69 bits |= code << (bits_left - nbits);
70 bits_left -= nbits;
71
72 while bits_left <= 32 {
73 out.put_u8((bits >> 32) as u8)?;
74
75 bits <<= 8;
76 bits_left += 8;
77 }
78 }
79
80 if bits_left != 40 {
81 // This writes the EOS token
82 bits |= (1 << bits_left) - 1;
83
84 out.put_u8((bits >> 32) as u8)?;
85 }
86
87 Ok(())
88 }
89
encode_output_length(src: &[u8], low: bool) -> Result<usize>90 pub fn encode_output_length(src: &[u8], low: bool) -> Result<usize> {
91 let mut bits: usize = 0;
92
93 for &b in src {
94 let b = if low { b.to_ascii_lowercase() } else { b };
95
96 let (nbits, _) = ENCODE_TABLE[b as usize];
97 bits += nbits;
98 }
99
100 let mut len = bits / 8;
101
102 if bits & 7 != 0 {
103 len += 1;
104 }
105
106 Ok(len)
107 }
108
109 struct Decoder {
110 state: usize,
111 maybe_eos: bool,
112 }
113
114 impl Decoder {
new() -> Decoder115 fn new() -> Decoder {
116 Decoder {
117 state: 0,
118 maybe_eos: false,
119 }
120 }
121
122 // Decodes 4 bits
decode4(&mut self, input: u8) -> Result<Option<u8>>123 fn decode4(&mut self, input: u8) -> Result<Option<u8>> {
124 const MAYBE_EOS: u8 = 1;
125 const DECODED: u8 = 2;
126 const ERROR: u8 = 4;
127
128 // (next-state, byte, flags)
129 let (next, byte, flags) = DECODE_TABLE[self.state][input as usize];
130
131 if flags & ERROR == ERROR {
132 // Data followed the EOS marker
133 return Err(Error::InvalidHuffmanEncoding);
134 }
135
136 let ret = if flags & DECODED == DECODED {
137 Some(byte)
138 } else {
139 None
140 };
141
142 self.state = next;
143 self.maybe_eos = flags & MAYBE_EOS == MAYBE_EOS;
144
145 Ok(ret)
146 }
147
is_final(&self) -> bool148 fn is_final(&self) -> bool {
149 self.state == 0 || self.maybe_eos
150 }
151 }
152
153 mod table;
154