ravenrs_graphics/
barcode.rs

1//! Barcodes: turns text into the modules a scanner reads. Pure logic, so every
2//! output draws the same code and it can be tested without drawing.
3
4use std::fmt::Write as _;
5
6use ravenrs_core::{Color, Rect};
7use serde::{Deserialize, Serialize};
8
9use crate::vector::{Shape, append_rectangle};
10
11/// A barcode format.
12#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
13#[serde(rename_all = "camelCase")]
14#[non_exhaustive]
15#[cfg_attr(feature = "live", ravenrs_live::expose(part = "variants"))]
16pub enum Symbology {
17    /// Code 128: any printable ASCII text, compact for digits.
18    #[default]
19    Code128,
20    /// Code 39: capitals, digits and `-. $/+%`.
21    Code39,
22    /// EAN-13: 12 digits, or 13 with the check digit.
23    Ean13,
24    /// EAN-8: 7 digits, or 8 with the check digit.
25    Ean8,
26    /// UPC-A: 11 digits, or 12 with the check digit.
27    UpcA,
28    /// Interleaved 2 of 5: an even number of digits.
29    Itf,
30    /// QR Code: any text.
31    Qr,
32}
33
34/// What a scanner reads.
35#[derive(Clone, Debug, PartialEq, Eq)]
36#[non_exhaustive]
37pub enum Pattern {
38    /// Modules from left to right; `true` is a bar.
39    Linear {
40        /// The modules.
41        modules: Vec<bool>,
42        /// The text printed under the bars, check digits included.
43        text: String,
44    },
45    /// Rows of square modules; `true` is dark.
46    Matrix {
47        /// How many modules on each side.
48        size: usize,
49        /// The modules, row by row.
50        cells: Vec<bool>,
51    },
52}
53
54/// Empty modules on each side of a linear code, which scanners need.
55const QUIET_LINEAR: f32 = 10.0;
56/// Empty modules around a QR Code, as its standard asks.
57const QUIET_MATRIX: f32 = 4.0;
58
59/// Encodes `data`, or says why it does not fit the format.
60pub fn encode(symbology: Symbology, data: &str) -> Result<Pattern, String> {
61    match symbology {
62        Symbology::Code128 => code128(data),
63        Symbology::Code39 => code39(data),
64        Symbology::Ean13 => ean13(data),
65        Symbology::Ean8 => ean8(data),
66        Symbology::UpcA => upc_a(data),
67        Symbology::Itf => itf(data),
68        Symbology::Qr => qr(data),
69    }
70}
71
72/// How many modules a pattern spans across, quiet zones included: drawn in a
73/// width that divides by this, every module lands on whole pixels.
74pub fn modules_across(pattern: &Pattern) -> usize {
75    match pattern {
76        Pattern::Linear { modules, .. } => modules.len() + 2 * QUIET_LINEAR as usize,
77        Pattern::Matrix { size, .. } => size + 2 * QUIET_MATRIX as usize,
78    }
79}
80
81/// The shape of a pattern inside `rect`, centered and with its quiet zone.
82pub fn shape(pattern: &Pattern, rect: Rect, color: Color) -> Shape {
83    let mut path = Vec::new();
84    match pattern {
85        Pattern::Linear { modules, .. } => {
86            let module = rect.width() / (modules.len() as f32 + 2.0 * QUIET_LINEAR);
87            let left = rect.x() + QUIET_LINEAR * module;
88            for (start, length) in runs(modules) {
89                let x = left + start as f32 * module;
90                append_rectangle(&mut path, x, rect.y(), x + length as f32 * module, rect.max_y(), 0.0);
91            }
92        }
93        Pattern::Matrix { size, cells } => {
94            let module = rect.width().min(rect.height()) / (*size as f32 + 2.0 * QUIET_MATRIX);
95            let side = *size as f32 * module;
96            let (left, top) =
97                (rect.x() + (rect.width() - side) / 2.0, rect.y() + (rect.height() - side) / 2.0);
98            for (row, cells) in cells.chunks((*size).max(1)).enumerate() {
99                let y = top + row as f32 * module;
100                for (start, length) in runs(cells) {
101                    let x = left + start as f32 * module;
102                    append_rectangle(&mut path, x, y, x + length as f32 * module, y + module, 0.0);
103                }
104            }
105        }
106    }
107    Shape::filled(path, color)
108}
109
110/// The start and length of each run of `true`.
111fn runs(modules: &[bool]) -> impl Iterator<Item = (usize, usize)> + '_ {
112    let mut at = 0;
113    std::iter::from_fn(move || {
114        while modules.get(at) == Some(&false) {
115            at += 1;
116        }
117        let start = at;
118        while modules.get(at) == Some(&true) {
119            at += 1;
120        }
121        (at > start).then_some((start, at - start))
122    })
123}
124
125/// Appends alternating bars and spaces, given as widths in modules, bar first.
126fn push_widths(modules: &mut Vec<bool>, widths: &str) {
127    for (index, width) in widths.bytes().enumerate() {
128        modules.extend(std::iter::repeat_n(index % 2 == 0, usize::from(width - b'0')));
129    }
130}
131
132/// Bar and space widths of each Code 128 symbol, by value; 106 is the stop.
133const CODE128: [&str; 107] = [
134    "212222", "222122", "222221", "121223", "121322", "131222", "122213", "122312", "132212", "221213",
135    "221312", "231212", "112232", "122132", "122231", "113222", "123122", "123221", "223211", "221132",
136    "221231", "213212", "223112", "312131", "311222", "321122", "321221", "312212", "322112", "322211",
137    "212123", "212321", "232121", "111323", "131123", "131321", "112313", "132113", "132311", "211313",
138    "231113", "231311", "112133", "112331", "132131", "113123", "113321", "133121", "313121", "211331",
139    "231131", "213113", "213311", "213131", "311123", "311321", "331121", "312113", "312311", "332111",
140    "314111", "221411", "431111", "111224", "111422", "121124", "121421", "141122", "141221", "112214",
141    "112412", "122114", "122411", "142112", "142211", "241211", "221114", "413111", "241112", "134111",
142    "111242", "121142", "121241", "114212", "124112", "124211", "411212", "421112", "421211", "212141",
143    "214121", "412121", "111143", "111341", "131141", "114113", "114311", "411113", "411311", "113141",
144    "114131", "311141", "411131", "211412", "211214", "211232", "2331112",
145];
146const CODE128_START_B: usize = 104;
147const CODE128_START_C: usize = 105;
148const CODE128_TO_C: usize = 99;
149const CODE128_TO_B: usize = 100;
150const CODE128_STOP: usize = 106;
151/// A run of this many digits is shorter in subset C even with the switches.
152const CODE128_DIGITS_FOR_C: usize = 6;
153
154fn code128(data: &str) -> Result<Pattern, String> {
155    if data.is_empty() {
156        return Err("Code 128 needs some text".to_owned());
157    }
158    let bytes = data.as_bytes();
159    if !bytes.iter().all(|b| (32..=126).contains(b)) {
160        return Err("Code 128 takes printable ASCII text".to_owned());
161    }
162    let digits_at = |at: usize| bytes[at..].iter().take_while(|b| b.is_ascii_digit()).count();
163    let mut symbols = Vec::new();
164    let mut in_c = digits_at(0) >= 4 && digits_at(0) % 2 == 0;
165    symbols.push(if in_c { CODE128_START_C } else { CODE128_START_B });
166    let mut at = 0;
167    while at < bytes.len() {
168        let digits = digits_at(at);
169        if in_c {
170            if digits >= 2 {
171                symbols.push(usize::from((bytes[at] - b'0') * 10 + (bytes[at + 1] - b'0')));
172                at += 2;
173                continue;
174            }
175            symbols.push(CODE128_TO_B);
176            in_c = false;
177        } else if digits >= CODE128_DIGITS_FOR_C {
178            // An odd digit goes first in B, so the pairs finish the run exactly.
179            if digits % 2 == 1 {
180                symbols.push(usize::from(bytes[at] - 32));
181                at += 1;
182            }
183            symbols.push(CODE128_TO_C);
184            in_c = true;
185            continue;
186        }
187        symbols.push(usize::from(bytes[at] - 32));
188        at += 1;
189    }
190    let check = symbols.iter().enumerate().map(|(i, s)| s * i.max(1)).sum::<usize>() % 103;
191    symbols.push(check);
192    symbols.push(CODE128_STOP);
193    let mut modules = Vec::new();
194    for symbol in symbols {
195        push_widths(&mut modules, CODE128[symbol]);
196    }
197    Ok(Pattern::Linear { modules, text: data.to_owned() })
198}
199
200const CODE39_CHARS: &str = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ-. $/+%*";
201/// Narrow and wide elements of each character above: bar, space, bar, and so on.
202const CODE39: [&str; 44] = [
203    "nnnwwnwnn",
204    "wnnwnnnnw",
205    "nnwwnnnnw",
206    "wnwwnnnnn",
207    "nnnwwnnnw",
208    "wnnwwnnnn",
209    "nnwwwnnnn",
210    "nnnwnnwnw",
211    "wnnwnnwnn",
212    "nnwwnnwnn",
213    "wnnnnwnnw",
214    "nnwnnwnnw",
215    "wnwnnwnnn",
216    "nnnnwwnnw",
217    "wnnnwwnnn",
218    "nnwnwwnnn",
219    "nnnnnwwnw",
220    "wnnnnwwnn",
221    "nnwnnwwnn",
222    "nnnnwwwnn",
223    "wnnnnnnww",
224    "nnwnnnnww",
225    "wnwnnnnwn",
226    "nnnnwnnww",
227    "wnnnwnnwn",
228    "nnwnwnnwn",
229    "nnnnnnwww",
230    "wnnnnnwwn",
231    "nnwnnnwwn",
232    "nnnnwnwwn",
233    "wwnnnnnnw",
234    "nwwnnnnnw",
235    "wwwnnnnnn",
236    "nwnnwnnnw",
237    "wwnnwnnnn",
238    "nwwnwnnnn",
239    "nwnnnnwnw",
240    "wwnnnnwnn",
241    "nwwnnnwnn",
242    "nwnwnwnnn",
243    "nwnwnnnwn",
244    "nwnnnwnwn",
245    "nnnwnwnwn",
246    "nwnnwnwnn",
247];
248/// How much wider a wide element is.
249const CODE39_WIDE: usize = 3;
250
251fn code39(data: &str) -> Result<Pattern, String> {
252    if data.is_empty() {
253        return Err("Code 39 needs some text".to_owned());
254    }
255    let upper = data.to_ascii_uppercase();
256    if let Some(bad) = upper.chars().find(|c| *c == '*' || !CODE39_CHARS.contains(*c)) {
257        return Err(format!("Code 39 does not have '{bad}'"));
258    }
259    let mut modules = Vec::new();
260    for c in std::iter::once('*').chain(upper.chars()).chain(std::iter::once('*')) {
261        let index = CODE39_CHARS.find(c).unwrap_or(0);
262        for (element, kind) in CODE39[index].bytes().enumerate() {
263            let width = if kind == b'w' { CODE39_WIDE } else { 1 };
264            modules.extend(std::iter::repeat_n(element % 2 == 0, width));
265        }
266        // The narrow gap between characters.
267        modules.push(false);
268    }
269    modules.pop();
270    Ok(Pattern::Linear { modules, text: upper })
271}
272
273/// The check digit of a GS1 number: weights 3 and 1 from the right.
274fn gs1_check(digits: &[u8]) -> u8 {
275    let sum: u32 =
276        digits.iter().rev().enumerate().map(|(i, d)| u32::from(*d) * if i % 2 == 0 { 3 } else { 1 }).sum();
277    ((10 - sum % 10) % 10) as u8
278}
279
280/// The digits of a GS1 number of `length`, adding the check digit or verifying it.
281fn gs1_digits(name: &str, data: &str, length: usize) -> Result<Vec<u8>, String> {
282    if !data.bytes().all(|b| b.is_ascii_digit()) {
283        return Err(format!("{name} takes only digits"));
284    }
285    let mut digits: Vec<u8> = data.bytes().map(|b| b - b'0').collect();
286    if digits.len() == length - 1 {
287        digits.push(gs1_check(&digits));
288    } else if digits.len() != length {
289        return Err(format!("{name} takes {} or {length} digits", length - 1));
290    } else if gs1_check(&digits[..length - 1]) != digits[length - 1] {
291        return Err(format!("{name}: the check digit of {data} is wrong"));
292    }
293    Ok(digits)
294}
295
296/// Widths of each digit's symbol in the odd-parity left set; the right set has
297/// the same widths, and the even-parity set the same widths reversed.
298const EAN_L: [&str; 10] = ["3211", "2221", "2122", "1411", "1132", "1231", "1114", "1312", "1213", "3112"];
299/// Which left digits use the even-parity set, by the first digit of an EAN-13.
300const EAN13_PARITY: [&str; 10] =
301    ["LLLLLL", "LLGLGG", "LLGGLG", "LLGGGL", "LGLLGG", "LGGLLG", "LGGGLL", "LGLGLG", "LGLGGL", "LGGLGL"];
302
303fn push_symbol(modules: &mut Vec<bool>, widths: &str, starts_dark: bool, reversed: bool) {
304    let mut ordered: Vec<u8> = widths.bytes().collect();
305    if reversed {
306        ordered.reverse();
307    }
308    for (index, width) in ordered.iter().enumerate() {
309        modules.extend(std::iter::repeat_n((index % 2 == 0) == starts_dark, usize::from(width - b'0')));
310    }
311}
312
313fn ean_modules(left: &[u8], parity: &str, right: &[u8]) -> Vec<bool> {
314    let mut modules = vec![true, false, true];
315    for (digit, set) in left.iter().zip(parity.bytes()) {
316        // Left symbols start with a space.
317        push_symbol(&mut modules, EAN_L[usize::from(*digit)], false, set == b'G');
318    }
319    modules.extend([false, true, false, true, false]);
320    for digit in right {
321        // Right symbols start with a bar.
322        push_symbol(&mut modules, EAN_L[usize::from(*digit)], true, false);
323    }
324    modules.extend([true, false, true]);
325    modules
326}
327
328fn digits_text(digits: &[u8]) -> String {
329    let mut text = String::with_capacity(digits.len());
330    for digit in digits {
331        let _ = write!(text, "{digit}");
332    }
333    text
334}
335
336fn ean13(data: &str) -> Result<Pattern, String> {
337    let digits = gs1_digits("EAN-13", data, 13)?;
338    let modules = ean_modules(&digits[1..7], EAN13_PARITY[usize::from(digits[0])], &digits[7..]);
339    Ok(Pattern::Linear { modules, text: digits_text(&digits) })
340}
341
342fn ean8(data: &str) -> Result<Pattern, String> {
343    let digits = gs1_digits("EAN-8", data, 8)?;
344    let modules = ean_modules(&digits[..4], "LLLL", &digits[4..]);
345    Ok(Pattern::Linear { modules, text: digits_text(&digits) })
346}
347
348fn upc_a(data: &str) -> Result<Pattern, String> {
349    let digits = gs1_digits("UPC-A", data, 12)?;
350    let modules = ean_modules(&digits[..6], "LLLLLL", &digits[6..]);
351    Ok(Pattern::Linear { modules, text: digits_text(&digits) })
352}
353
354/// Narrow and wide bars of each digit in Interleaved 2 of 5.
355const ITF: [&str; 10] =
356    ["nnwwn", "wnnnw", "nwnnw", "wwnnn", "nnwnw", "wnwnn", "nwwnn", "nnnww", "wnnwn", "nwnwn"];
357const ITF_WIDE: usize = 3;
358
359fn itf(data: &str) -> Result<Pattern, String> {
360    if data.is_empty() || !data.bytes().all(|b| b.is_ascii_digit()) {
361        return Err("Interleaved 2 of 5 takes only digits".to_owned());
362    }
363    if !data.len().is_multiple_of(2) {
364        return Err("Interleaved 2 of 5 takes an even number of digits".to_owned());
365    }
366    let mut modules = vec![true, false, true, false];
367    let width = |kind: u8| if kind == b'w' { ITF_WIDE } else { 1 };
368    for pair in data.as_bytes().chunks(2) {
369        let bars = ITF[usize::from(pair[0] - b'0')].as_bytes();
370        let spaces = ITF[usize::from(pair[1] - b'0')].as_bytes();
371        for (bar, space) in bars.iter().zip(spaces) {
372            modules.extend(std::iter::repeat_n(true, width(*bar)));
373            modules.extend(std::iter::repeat_n(false, width(*space)));
374        }
375    }
376    modules.extend(std::iter::repeat_n(true, ITF_WIDE));
377    modules.extend([false, true]);
378    Ok(Pattern::Linear { modules, text: data.to_owned() })
379}
380
381fn qr(data: &str) -> Result<Pattern, String> {
382    if data.is_empty() {
383        return Err("a QR Code needs some text".to_owned());
384    }
385    let code = qrcodegen::QrCode::encode_text(data, qrcodegen::QrCodeEcc::Medium)
386        .map_err(|_| "the text is too long for a QR Code".to_owned())?;
387    let size = code.size();
388    let cells =
389        (0..size).flat_map(|y| (0..size).map(move |x| (x, y))).map(|(x, y)| code.get_module(x, y)).collect();
390    Ok(Pattern::Matrix { size: size as usize, cells })
391}
392
393#[cfg(test)]
394mod tests {
395    use super::*;
396    use crate::vector::PathSegment;
397
398    fn modules(symbology: Symbology, data: &str) -> Vec<bool> {
399        match encode(symbology, data) {
400            Ok(Pattern::Linear { modules, .. }) => modules,
401            other => panic!("{other:?}"),
402        }
403    }
404
405    fn text(symbology: Symbology, data: &str) -> String {
406        match encode(symbology, data) {
407            Ok(Pattern::Linear { text, .. }) => text,
408            other => panic!("{other:?}"),
409        }
410    }
411
412    fn bits(modules: &[bool]) -> String {
413        modules.iter().map(|m| if *m { '1' } else { '0' }).collect()
414    }
415
416    #[test]
417    fn the_code128_table_is_consistent() {
418        let mut seen = std::collections::HashSet::new();
419        for (value, widths) in CODE128.iter().enumerate() {
420            let total: u32 = widths.bytes().map(|b| u32::from(b - b'0')).sum();
421            assert_eq!(total, if value == CODE128_STOP { 13 } else { 11 }, "{value}");
422            assert!(seen.insert(widths), "{value} is repeated");
423        }
424    }
425
426    #[test]
427    fn code128_has_the_known_check_symbol() {
428        // 104 + 48*1 + 42*2 + 42*3 + 17*4 + 18*5 + 19*6 + 35*7 = 879, and 879 mod 103 = 55.
429        let symbols_end = modules(Symbology::Code128, "PJJ123C");
430        let expected: String = [CODE128_START_B, 48, 42, 42, 17, 18, 19, 35, 55, CODE128_STOP]
431            .iter()
432            .flat_map(|s| {
433                let mut part = Vec::new();
434                push_widths(&mut part, CODE128[*s]);
435                part
436            })
437            .map(|m| if m { '1' } else { '0' })
438            .collect();
439        assert_eq!(bits(&symbols_end), expected);
440    }
441
442    #[test]
443    fn code128_uses_pairs_for_digits() {
444        assert!(
445            modules(Symbology::Code128, "12345678").len() < modules(Symbology::Code128, "1234567A").len()
446        );
447        // Odd, mixed and long runs all encode without leaving digits behind.
448        for data in ["1", "12", "123", "1234", "12345", "A123456", "A1234567", "1234567", "12A34", "123456A"]
449        {
450            assert!(encode(Symbology::Code128, data).is_ok(), "{data}");
451        }
452    }
453
454    #[test]
455    fn check_digits_are_added_or_verified() {
456        assert_eq!(text(Symbology::Ean13, "400638133393"), "4006381333931");
457        assert_eq!(text(Symbology::Ean13, "4006381333931"), "4006381333931");
458        assert!(encode(Symbology::Ean13, "4006381333932").is_err());
459        assert_eq!(text(Symbology::Ean8, "9638507"), "96385074");
460        assert_eq!(text(Symbology::UpcA, "03600029145"), "036000291452");
461        assert!(encode(Symbology::Ean13, "12345").is_err());
462        assert!(encode(Symbology::Ean13, "abcdefghijkl").is_err());
463    }
464
465    #[test]
466    fn gs1_codes_have_their_standard_lengths() {
467        assert_eq!(modules(Symbology::Ean13, "4006381333931").len(), 95);
468        assert_eq!(modules(Symbology::Ean8, "96385074").len(), 67);
469        assert_eq!(modules(Symbology::UpcA, "036000291452").len(), 95);
470    }
471
472    #[test]
473    fn code39_refuses_what_it_does_not_have() {
474        assert_eq!(text(Symbology::Code39, "abc-1"), "ABC-1");
475        assert!(encode(Symbology::Code39, "a*b").is_err());
476        assert!(encode(Symbology::Code39, "ç").is_err());
477        assert!(encode(Symbology::Code39, "").is_err());
478    }
479
480    #[test]
481    fn itf_needs_an_even_number_of_digits() {
482        assert!(encode(Symbology::Itf, "1234").is_ok());
483        assert!(encode(Symbology::Itf, "123").is_err());
484        assert!(encode(Symbology::Itf, "12a4").is_err());
485    }
486
487    #[test]
488    fn qr_codes_are_square_with_finder_patterns() {
489        let Ok(Pattern::Matrix { size, cells }) = encode(Symbology::Qr, "https://example.com") else {
490            panic!()
491        };
492        assert_eq!(cells.len(), size * size);
493        assert_eq!((size - 21) % 4, 0, "a valid version");
494        assert!(cells[..7].iter().all(|c| *c), "top of the finder pattern");
495        assert!(encode(Symbology::Qr, "").is_err());
496        assert!(encode(Symbology::Qr, &"x".repeat(5000)).is_err());
497    }
498
499    #[test]
500    fn shapes_stay_inside_their_box_and_keep_the_quiet_zone() {
501        let rect = Rect::new(10.0, 20.0, 200.0, 50.0);
502        for (symbology, data) in
503            [(Symbology::Code128, "ABC123"), (Symbology::Qr, "x"), (Symbology::Ean13, "400638133393")]
504        {
505            let pattern = encode(symbology, data).map_err(|e| e.to_string());
506            let drawn = shape(&pattern.unwrap_or_else(|e| panic!("{e}")), rect, Color::BLACK);
507            assert!(!drawn.path.is_empty());
508            for segment in &drawn.path {
509                if let PathSegment::Move(p) | PathSegment::Line(p) = segment {
510                    assert!(p.x > rect.x() && p.x < rect.max_x() + 0.001, "{p:?}");
511                    assert!(p.y >= rect.y() - 0.001 && p.y <= rect.max_y() + 0.001, "{p:?}");
512                }
513            }
514        }
515    }
516}
ravenrs_graphics/barcode.rs

ravenrs_graphics/
barcode.rs
