| 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 |
} |