Debian Codegraph @

.cargo/vendor/fax_derive/src/lib.rs

raw
1 use proc_macro2::{TokenStream, Span, Literal};
2 use quote::{quote, ToTokens};
3 use syn::{
4 parse_macro_input, Expr, Error, parse::{ParseStream, Parse}, Result, Token, Ident,
5 punctuated::Punctuated, braced, Type,
6 };
7 use std::fmt::{self, Debug};
8 use std::ops::Range;
9
10 #[proc_macro]
11 pub fn bitmaps(input: proc_macro::TokenStream) -> proc_macro::TokenStream {
12 // Parse the input tokens into a syntax tree
13 let input = parse_macro_input!(input as BitMaps);
14
15 // Build the output, possibly using quasi-quotation
16 let maps = input.maps.iter().map(|map| {
17 let (code, root) = map.build();
18 let name = &map.name;
19 let typ = match map.typ {
20 Some(ref t) => quote!{ #t },
21 None => quote! { u16 }
22 };
23 let list = map.entries.iter().map(|entry| {
24 let bits = entry.bits;
25 let val = &entry.value;
26 quote!{ (#val, #bits) }
27 });
28 let arms = map.entries.iter().map(|entry| {
29 let bits = entry.bits;
30 let val = &entry.value;
31 quote!{ #val => #bits }
32 });
33 let n = map.entries.len();
34
35 quote! {
36 pub mod #name {
37 pub use super::*;
38 use crate::{BitReader, Bits};
39
40 #code
41
42 pub fn decode(reader: &mut impl BitReader) -> Option<#typ> {
43 let root = #root;
44 root.find(reader)
45 }
46
47 pub fn encode(val: #typ) -> Option<Bits> {
48 let bits = match val {
49 #(#arms,)*
50 _ => return None
51 };
52 Some(bits)
53 }
54
55 pub static ENTRIES: [(#typ, Bits); #n] = [ #(#list,)* ];
56 }
57 }
58 });
59 let expanded = quote! {
60 #(#maps)*
61 };
62
63 // Hand the output tokens back to the compiler
64 proc_macro::TokenStream::from(expanded)
65 }
66
67 struct BitMaps {
68 maps: Vec<BitMap>
69 }
70 impl Parse for BitMaps {
71 fn parse(input: ParseStream) -> Result<Self> {
72 let entries = Punctuated::<_, Token![,]>::parse_terminated(input)?;
73
74 Ok(BitMaps { maps: entries.into_pairs().map(|p| p.into_value()).collect() })
75 }
76 }
77
78 struct BitMap {
79 name: Ident,
80 entries: Vec<BitMapEntry>,
81 typ: Option<Type>
82 }
83 impl Parse for BitMap {
84 fn parse(input: ParseStream) -> Result<Self> {
85 let name: Ident = input.parse()?;
86 let typ;
87 if input.peek(Token![<]) {
88 let _ = input.parse::<Token![<]>()?;
89 typ = Some(input.parse::<Type>()?);
90 let _ = input.parse::<Token![>]>()?;
91 } else {
92 typ = None;
93 }
94
95 let content;
96
97 braced!(content in input);
98 let entries = Punctuated::<_, Token![,]>::parse_terminated(&content)?;
99
100 Ok(BitMap {
101 name, typ,
102 entries: entries.into_pairs().map(|p| p.into_value()).collect()
103 })
104 }
105 }
106 impl BitMap {
107 fn build(&self) -> (TokenStream, TokenStream) {
108 let patterns: Vec<(usize, Bits)> = self.entries.iter().enumerate().map(|(i, e)| (i, e.bits)).collect();
109 let node = Node::build(&patterns).unwrap();
110
111 let mut defs = vec![];
112 let out = self.walk(&mut defs, &node, Bits::empty());
113
114 (quote! {
115 #(#defs)*
116 }, out)
117 }
118 fn walk(&self, defs: &mut Vec<TokenStream>, node: &Node<usize>, bits: Bits) -> TokenStream {
119 match *node {
120 Node::Value(idx, len) => {
121 let val = &self.entries[idx].value;
122 quote!{ Entry::Value(#val, #len) }
123 }
124 Node::LeafLut(ref lut) => {
125 let name = Ident::new(&format!("LEAF_LUT_{}", bits), Span::call_site());
126 let size = lut.data.len();
127 let width = lut.width;
128 let entries = lut.data.iter().map(|e| match *e {
129 Some((idx, len)) => {
130 let val = &self.entries[idx].value;
131 quote! { Some((#val, #len)) }
132 },
133 None => quote!{ None }
134 });
135 let typ = match self.typ {
136 Some(ref t) => quote!{ #t },
137 None => quote! { u16 }
138 };
139 defs.push(quote!{
140 static #name: [Option<(#typ, u8)>; #size] = [
141 #(#entries,)*
142 ];
143 });
144 quote! { Entry::Leaf(#width, &#name) }
145 }
146 Node::PrefixLut(ref lut) => {
147 let name = Ident::new(&format!("PREFIX_LUT_{}", bits), Span::call_site());
148 let size = 1usize << lut.width;
149 let width = lut.width;
150 let entries: Vec<_> = lut.data.iter().enumerate().map(|(i, node)| match node {
151 None => quote!{ Entry::Empty }.into(),
152 Some(node) => {
153 let entry_bits = bits.concat(Bits::new(i as u16, lut.width));
154 self.walk(defs, node, entry_bits)
155 }
156 }).collect();
157
158 let typ = match self.typ {
159 Some(ref t) => quote!{ Entry<#t> },
160 None => quote! { Entry<u16> }
161 };
162 defs.push(quote!{
163 static #name: [#typ; #size] = [
164 #(#entries,)*
165 ];
166 });
167
168 quote! { Entry::Prefix(#width, &#name) }
169 }
170 }
171 }
172 }
173 struct BitMapEntry {
174 bits: Bits,
175 value: Expr,
176 }
177 impl Parse for BitMapEntry {
178 fn parse(input: ParseStream) -> Result<Self> {
179 let bits = input.parse()?;
180 let _ = input.parse::<Token![=>]>()?;
181 let value = input.parse()?;
182 Ok(BitMapEntry { bits, value })
183 }
184 }
185
186 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
187 struct Bits {
188 data: u16,
189 len: u8
190 }
191 impl Bits {
192 fn new(data: u16, len: u8) -> Bits {
193 Bits { data, len }
194 }
195 fn concat(self, rhs: Bits) -> Bits {
196 Bits {
197 data: self.data << rhs.len | rhs.data,
198 len: self.len + rhs.len
199 }
200 }
201 fn common_prefix_len(self, other: Bits) -> u8 {
202 (self.align_left() ^ other.align_left()).leading_zeros() as u8
203 }
204 fn align_left(self) -> u16 {
205 self.data << (16 - self.len)
206 }
207 fn prefix(self, len: u8) -> u16 {
208 assert!(len <= self.len);
209 self.data >> (self.len - len)
210 }
211 fn prefix_range(self, len: u8) -> Range<u16> {
212 assert!(len >= self.len);
213 let s = len - self.len;
214 let n = 1 << (len - self.len);
215 let m = self.data << s;
216 m .. m + n
217 }
218 fn strip_prefix(self, len: u8) -> Bits {
219 assert!(len <= self.len);
220 let len = self.len - len;
221 Bits {
222 data: self.data & ((1<<len)-1),
223 len
224 }
225 }
226 fn empty() -> Bits {
227 Bits {
228 data: 0,
229 len: 0
230 }
231 }
232 }
233 impl fmt::Display for Bits {
234 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
235 write!(f, "{:0w$b}", self.data, w=self.len as usize)
236 }
237 }
238 impl fmt::Debug for Bits {
239 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
240 write!(f, "d={:0b} w={}", self.data, self.len)
241 }
242 }
243 impl ToTokens for Bits {
244 fn to_tokens(&self, tokens: &mut TokenStream) {
245 let Bits { data, len } = *self;
246 tokens.extend(quote! {
247 Bits { data: #data, len: #len }
248 })
249 }
250 }
251 impl Parse for Bits {
252 fn parse(input: ParseStream) -> Result<Self> {
253 let lit: Literal = input.parse()?;
254
255 let mut data = 0;
256 let mut len = 0;
257 let s = lit.to_string();
258 for c in s.chars() {
259 let b = match c {
260 '0' => 0,
261 '1' => 1,
262 _ => return Err(Error::new(lit.span(), "only 0 and 1 are allowed"))
263 };
264 data = data << 1 | b;
265 len += 1;
266 }
267 Ok(Bits { data, len })
268 }
269 }
270
271 struct LeafLut<T> {
272 width: u8,
273 data: Vec<Option<(T, u8)>>
274 }
275 impl<T: Clone> LeafLut<T> {
276 fn build(patterns: &[(T, Bits)], prefix: u8, width: u8) -> Self {
277 assert!(patterns.len() > 1);
278
279 let mut data = vec![None; 1usize << width];
280 for (val, pat) in patterns {
281 let pat = pat.strip_prefix(prefix);
282
283 for idx in pat.prefix_range(width) {
284 data[idx as usize] = Some((val.clone(), pat.len));
285 }
286 }
287
288 assert!(data.len() > 1);
289 LeafLut {
290 data,
291 width
292 }
293 }
294 }
295 enum Node<T> {
296 Value(T, u8),
297 LeafLut(LeafLut<T>),
298 PrefixLut(PrefixLut<T>)
299 }
300 impl<T: Copy + Default + Debug> Node<T> {
301 fn size(&self) -> usize {
302 match self {
303 Node::Value(_, _) => 1,
304 Node::LeafLut(ref lut) => 1 << lut.width,
305 Node::PrefixLut(ref lut) => lut.size(),
306 }
307 }
308 fn cost(&self) -> f64 {
309 match self {
310 Node::Value(_, _) => 0.0,
311 Node::LeafLut(_) => 1.0,
312 Node::PrefixLut(ref lut) => lut.cost(),
313 }
314 }
315 fn build(patterns: &[(T, Bits)]) -> Option<Node<T>> {
316 Self::build_prefix(patterns, 0)
317 }
318 fn build_prefix(patterns: &[(T, Bits)], prefix: u8) -> Option<Node<T>> {
319 //debug!("{:?}", patterns);
320 match patterns.len() {
321 0 => None,
322 1 => {
323 let (val, bits) = patterns[0];
324 Some(Node::Value(val, bits.len))
325 }
326 _ => {
327 let width = patterns.iter().map(|(_, b)| b.len).max().unwrap() - prefix;
328 if width > 8 {
329 Some(Node::PrefixLut(PrefixLut::build(&patterns, prefix)))
330 } else {
331 Some(Node::LeafLut(LeafLut::build(patterns, prefix, width) ))
332 }
333 }
334 }
335 }
336 }
337
338 struct PrefixLut<T> {
339 width: u8,
340 data: Vec<Option<Node<T>>>
341 }
342 impl<T: Copy + Default + Debug> PrefixLut<T> {
343 fn size(&self) -> usize {
344 self.data.iter().filter_map(|o| o.as_ref().map(|n| n.size())).sum::<usize>() + self.data.len()
345 }
346 // cost per 1 bit
347 fn cost(&self) -> f64 {
348 self.data.iter().filter_map(|o| o.as_ref().map(|n| n.cost())).sum::<f64>() * 0.5f64.powi(-(self.width as i32))
349 }
350 fn build(patterns: &[(T, Bits)], prefix: u8) -> Self {
351 // determine LUT size
352 let max_width = patterns.iter().map(|(_, b)| b.len).max().unwrap() - prefix;
353
354 let mut best = None;
355 let mut best_cost = f64::INFINITY;
356 for w in max_width.min(4) .. max_width {
357 let lut = Self::build_width(patterns, w, prefix);
358 let cost = lut.cost();
359 if cost < best_cost {
360 best_cost = cost;
361 best = Some(lut);
362 }
363 }
364 best.expect("empty results")
365 }
366 fn build_width(patterns: &[(T, Bits)], width: u8, prefix: u8) -> Self {
367 let mut slots = vec![vec![]; 1 << width];
368 //dbg!(patterns);
369 for &(val, bits) in patterns {
370 let bits = bits.strip_prefix(prefix);
371 //debug!("{} - {}bits ({:?})", bits, width, val);
372
373 if bits.len >= width {
374 //debug!(" = {}", bits.strip_prefix(width));
375 slots[bits.prefix(width) as usize].push((val, bits));
376 } else {
377 for k in bits.prefix_range(width) {
378 //debug!(" -> {}", k);
379 slots[k as usize].push((val, bits));
380 }
381 }
382 }
383
384 let data: Vec<_> = slots.iter().map(|patterns| Node::build_prefix(&patterns, width)).collect();
385
386 PrefixLut {
387 data,
388 width
389 }
390 }
391 }