steiner_tree/
serialization.rs

1// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
2//
3// SPDX-License-Identifier: GPL-3.0-or-later
4
5//! Convert the lookup-table to and from a compact binary representation.
6
7use super::lut::LookupTable;
8use super::marker_types::Canonical;
9use super::minimum_spanning_tree::minimum_spanning_tree_hamming_space;
10use super::*;
11use lut::ValuesOrRedirect;
12use num_traits::{FromPrimitive, Num, One, PrimInt, Signed, ToPrimitive, Unsigned, Zero};
13use point::*;
14use smallvec::SmallVec;
15use std::collections::HashMap;
16use std::fmt;
17use std::io::{Read, Write};
18use tree::*;
19
20type UInt = u32;
21type SInt = i32;
22
23/// Beginning of the LUT file.
24const MAGIC: &[u8] = "fast-steiner lookup-table\r\n".as_bytes();
25
26/// Serialize the lookup table.
27pub fn write_lut<W: Write>(writer: &mut W, lut: &LookupTable) -> Result<(), LUTWriteError> {
28    // Extract all trees.
29    let mut trees: Vec<_> = lut
30        .sub_lut_by_degree
31        .iter()
32        .flat_map(|sub_lut| sub_lut.values.iter())
33        .filter_map(|v| match v {
34            ValuesOrRedirect::Values(v) => Some(v),
35            ValuesOrRedirect::Redirect { .. } => None,
36        })
37        .flat_map(|v| v.iter())
38        .map(|v| &v.potential_optimal_steiner_tree)
39        .collect();
40    trees.sort_unstable();
41
42    // Reorder trees such that minimal storage is needed when storing only difference between trees.
43    println!("Compress {} trees.", trees.len());
44
45    {
46        // TODO: Create a minimum-spanning tree of the trees where the distance is the Hamming distance (of tree edges).
47        println!("Convert trees to bit vectors...");
48        let trees_as_bit_vectors: Vec<_> = trees.iter().map(|t| t.to_bitvec()).collect();
49
50        println!("Compute minimum spanning tree of trees (under Hamming distance)...");
51        let mst = minimum_spanning_tree_hamming_space(&trees_as_bit_vectors, true);
52    }
53
54    println!("Write trees...");
55    write_trees(writer, &trees)?;
56
57    Ok(())
58}
59
60fn write_trees<W: Write>(
61    writer: &mut W,
62    trees: &Vec<&Tree<Canonical>>,
63) -> Result<(), LUTWriteError> {
64    // Write number of trees.
65    write_unsigned_integer(writer, trees.len())?;
66
67    let empty_tree = Tree::empty_canonical();
68    let mut prev_tree = &empty_tree;
69    for current_tree in trees {
70        let (edge_diff_horiz, edge_diff_vert): (Vec<_>, Vec<_>) = prev_tree
71            .symmetric_difference(current_tree)
72            .partition(|e| e.is_horizontal());
73
74        // Number of differing edges.
75        write_unsigned_integer(writer, edge_diff_horiz.len())?;
76        write_unsigned_integer(writer, edge_diff_vert.len())?;
77
78        // Write differences in horizontal edges.
79        for e in edge_diff_horiz {
80            write_point_u4(writer, e.start())?;
81        }
82        // Write differences in vertical edges.
83        for e in edge_diff_vert {
84            write_point_u4(writer, e.start())?;
85        }
86
87        prev_tree = current_tree;
88    }
89
90    Ok(())
91}
92
93/// Write coordinates of the point as two 4-bit integers packed into a byte.
94fn write_point_u4<W: Write>(writer: &mut W, p: Point<HananCoord>) -> Result<(), LUTWriteError> {
95    assert!(
96        p.x < 16 && p.y < 16,
97        "edge coordinate out of range for storage"
98    );
99
100    let nibbles = ((p.x << 4) | (p.y & 0xf)) as u8;
101    writer.write_all(&[nibbles])?;
102    Ok(())
103}
104
105fn read_point<R: Read>(reader: &mut R) -> Result<Point<HananCoord>, LUTReadError> {
106    let nibbles = read_byte(reader)?;
107    let x = nibbles >> 4;
108    let y = nibbles & 0xf;
109    Ok(Point::new(x as HananCoord, y as HananCoord))
110}
111
112fn read_byte<R: Read>(reader: &mut R) -> Result<u8, LUTReadError> {
113    let mut b = [0u8];
114    reader.read_exact(&mut b)?;
115    Ok(b[0])
116}
117
118/// Convert bit strings into byte strings.
119/// This is used only for tests.
120#[cfg(test)]
121fn bits(bit_string: &str) -> Vec<u8> {
122    bit_string
123        .split_ascii_whitespace()
124        .map(|s| u8::from_str_radix(s, 2).unwrap())
125        .collect()
126}
127
128/// Shorthand notation for creating byte strings from the bit representation.
129/// This is used only for tests.
130#[cfg(test)]
131macro_rules! bits {
132    ($x:expr) => {
133        &mut bits($x)[..].as_ref()
134    };
135}
136
137/// Error during reading of the lookup table.
138#[derive(Debug)]
139pub enum LUTReadError {
140    /// General IO error.
141    IOError(std::io::Error),
142    /// End of file reached.
143    UnexpectedEndOfFile,
144    /// Something is wrong with the file format.
145    FormatError,
146}
147
148impl fmt::Display for LUTReadError {
149    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
150        use LUTReadError::*;
151        match self {
152            LUTReadError::FormatError => write!(f, "illegal table format"),
153            other => other.fmt(f),
154        }
155    }
156}
157
158/// Error types for writing LUT.
159#[derive(Debug)]
160pub enum LUTWriteError {
161    /// General IO error.
162    IOError(std::io::Error),
163}
164
165impl fmt::Display for LUTWriteError {
166    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
167        use LUTWriteError::*;
168        match self {
169            IOError(ioerr) => ioerr.fmt(f),
170        }
171    }
172}
173
174impl From<std::io::Error> for LUTReadError {
175    fn from(err: std::io::Error) -> Self {
176        match err.kind() {
177            std::io::ErrorKind::UnexpectedEof => LUTReadError::UnexpectedEndOfFile,
178            _ => LUTReadError::IOError(err),
179        }
180    }
181}
182
183impl From<std::io::Error> for LUTWriteError {
184    fn from(err: std::io::Error) -> Self {
185        match err.kind() {
186            _ => LUTWriteError::IOError(err),
187        }
188    }
189}
190
191/// Read the magic string at the beginning of the LUT file.
192/// Returns an error if the magic value is wrong.
193fn read_magic<R: Read>(reader: &mut R) -> Result<(), LUTReadError> {
194    // Read the magic string.
195    let mut buf = [0u8; MAGIC.len()];
196    reader.read_exact(&mut buf)?;
197
198    // Compare the buffer with the magic string.
199    match buf.as_ref() {
200        MAGIC => Ok(()), // Matic string is correct.
201        _ => {
202            let s = String::from_utf8_lossy(&buf);
203            log::error!(
204                "wrong file format, magic string is wrong: '{:?}', hex = '{:02x?}'",
205                s,
206                buf
207            );
208            Err(LUTReadError::FormatError)
209        } // Magic string is wrong.
210    }
211}
212
213/// Write the magic string at the beginning of the LUT file.
214fn write_magic<W: Write>(writer: &mut W) -> Result<(), LUTWriteError> {
215    writer.write_all(MAGIC)?;
216    Ok(())
217}
218
219/// Read an unsigned integer.
220/// Unsigned integers are stored as variable-length byte continuations.
221/// The all but last bytes of the continuation have the MSB set to one.
222/// The result is the concatenation of the 7 lower-value bits.
223/// The low-order byte appears first.
224fn read_unsigned_integer<T, R: Read>(reader: &mut R) -> Result<T, LUTReadError>
225where
226    T: PrimInt + Zero + FromPrimitive,
227{
228    // Read byte continuation until the most significant bit is zero.
229    let mut bytes = <SmallVec<[u8; 8]>>::new();
230    for b in reader.bytes() {
231        let b = b?;
232        bytes.push(b);
233        if b & 0x80 == 0 {
234            break;
235        }
236    }
237    if bytes.last().map(|b| b & 0x80) != Some(0) {
238        // Last byte must have MSB set to zero.
239        // Reached EOF.
240        Err(LUTReadError::UnexpectedEndOfFile)
241    } else {
242        Ok(bytes
243            .iter()
244            .rev()
245            .map(|b| b & 0x7f) // Set MSB to zero.
246            .fold(T::zero(), |acc, b| T::from_u8(b).unwrap() + (acc << 7)))
247    }
248}
249
250#[test]
251fn test_read_unsigned_integer() {
252    // Test values from LUT specification draft.
253    assert_eq!(
254        read_unsigned_integer::<u32, _>(bits!("00000000")).unwrap(),
255        0
256    );
257    assert_eq!(
258        read_unsigned_integer::<i32, _>(bits!("01111111")).unwrap(),
259        127
260    );
261    assert_eq!(
262        read_unsigned_integer::<i32, _>(bits!("10000000 00000001")).unwrap(),
263        128
264    );
265    assert_eq!(
266        read_unsigned_integer::<i32, _>(bits!("11111111 01111111")).unwrap(),
267        16383
268    );
269    assert_eq!(
270        read_unsigned_integer::<i32, _>(bits!("10000000 10000000 00000001")).unwrap(),
271        16384
272    );
273
274    // Empty bytes should raise an error.
275    assert!(read_unsigned_integer::<i32, _>(bits!("")).is_err());
276    // The last byte must always have the MSB set to zero.
277    assert!(read_unsigned_integer::<i32, _>(bits!("10000000")).is_err());
278}
279
280/// Write an unsigned integer.
281/// Unsigned integers are stored as variable-length byte continuations.
282/// The all but last bytes of the continuation have the MSB set to one.
283/// The result is the concatenation of the 7 lower-value bits.
284/// The low-order byte appears first.
285fn write_unsigned_integer<T, W: Write>(writer: &mut W, value: T) -> Result<(), LUTWriteError>
286where
287    T: PrimInt + Unsigned + FromPrimitive + ToPrimitive,
288{
289    let mut value = value;
290
291    let mask = T::from_u8(0x7f).unwrap();
292    let _0x80 = T::from_u8(0x80).unwrap();
293    while value > mask {
294        let lowest = (value & mask).to_u8().unwrap();
295        writer.write_all(&[0x80 | lowest])?; // Set the MSB.
296        value = value.shr(7);
297    }
298    debug_assert!(value & _0x80 == T::zero());
299    writer.write_all(&[value.to_u8().unwrap()])?;
300    Ok(())
301}
302
303#[test]
304fn test_write_unsigned_integer() {
305    // Test values from LUT specification draft.
306
307    fn test(num: UInt, expected: Vec<u8>) {
308        let mut buf = Vec::new();
309        write_unsigned_integer(&mut buf, num).unwrap();
310        assert_eq!(buf, expected);
311    }
312
313    test(0, vec![0x00]);
314    test(1, vec![0x01]);
315    test(127, vec![0x7f]);
316    test(128, vec![0x80, 0x01]);
317    test(16383, vec![0xff, 0x7f]);
318    test(16384, vec![0x80, 0x80, 0x01]);
319}
320
321/// Read a signed integer.
322/// The format is the same as for unsigned integers except that the sign bit
323/// is stored in the LSB of the lowest-order byte.
324fn read_signed_integer<T, R: Read>(reader: &mut R) -> Result<T, LUTReadError>
325where
326    T: PrimInt + Num + Zero + One + Signed + FromPrimitive,
327{
328    let u: T = read_unsigned_integer(reader)?;
329    let sign = u & One::one();
330
331    let magnitude = u.unsigned_shr(1);
332
333    Ok(if sign.is_one() {
334        T::zero() - magnitude
335    } else {
336        magnitude
337    })
338}
339
340#[test]
341fn test_read_signed_integer() {
342    // Test values from LUT specification draft.
343    assert_eq!(read_signed_integer::<i32, _>(bits!("00")).unwrap(), 0);
344    assert_eq!(read_signed_integer::<i32, _>(bits!("10")).unwrap(), 1);
345    assert_eq!(read_signed_integer::<i32, _>(bits!("11")).unwrap(), -1);
346    assert_eq!(
347        read_signed_integer::<i32, _>(bits!("01111110")).unwrap(),
348        63
349    );
350    assert_eq!(
351        read_signed_integer::<i32, _>(bits!("10000001 00000001")).unwrap(),
352        -64
353    );
354    assert_eq!(
355        read_signed_integer::<i32, _>(bits!("11111110 01111111")).unwrap(),
356        8191
357    );
358    assert_eq!(
359        read_signed_integer::<i32, _>(bits!("10000001 10000000 00000001")).unwrap(),
360        -8192
361    );
362
363    // Empty bytes should raise an error.
364    assert!(read_signed_integer::<i32, _>(bits!("")).is_err());
365    // The last byte must always have the MSB set to zero.
366    assert!(read_signed_integer::<i32, _>(bits!("10000000")).is_err());
367}
368
369/// Write a signed integer.
370/// The format is the same as for unsigned integers except that the sign bit
371/// is stored in the LSB of the lowest-order byte.
372fn write_signed_integer<W: Write>(writer: &mut W, value: SInt) -> Result<(), LUTWriteError> {
373    // Determine the sign bit.
374    let (sign, value) = if value < 0 { (1, -value) } else { (0, value) };
375
376    // Insert the sign bit at the lowest value bit position.
377    let magnitude = (value << 1) as UInt;
378    let u = magnitude | sign;
379
380    write_unsigned_integer(writer, u)
381}
382
383#[test]
384fn test_write_signed_integer() {
385    // Test values from LUT specification draft.
386
387    fn test(num: SInt, expected: Vec<u8>) {
388        let mut buf = Vec::new();
389        write_signed_integer(&mut buf, num).unwrap();
390        assert_eq!(buf, expected);
391    }
392
393    test(0, vec![0x00]);
394    test(1, vec![0b10]);
395    test(-1, vec![0b11]);
396    test(63, vec![0b01111110]);
397    test(-64, vec![0x81, 0x01]);
398    test(8191, vec![0b11111110, 0b01111111]);
399    test(-8192, vec![0b10000001, 0b10000000, 0b1]);
400}
401
402#[test]
403fn test_write_lut() {
404    let lut = super::gen_lut::gen_full_lut(4);
405
406    let mut buffer = Vec::new();
407
408    let write_result = write_lut(&mut buffer, &lut);
409    assert!(write_result.is_ok());
410    dbg!(buffer.len());
411    assert!(buffer.len() < 100);
412}
steiner_tree/serialization.rs

steiner_tree/
serialization.rs
