MOS substitution: Difference between revisions

← Older edit Newer edit →

VisualWikitext

@@ Line 39: / Line 39: @@
 == Algorithm ==
 Rust code for generating MOS substitution scales:
-<syntaxhighlight lang="rs>
+<syntaxhighlight lang="rs>pub type Letter = usize;
+/// Return gcd(a, b) and the Bezout coefficients: (g, x, y).
+pub fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
+    let (mut r, mut old_r) = (a, b);
+    let (mut s, mut old_s) = (1, 0);
+    let (mut t, mut old_t) = (0, 1);
+    while r != 0 {
+        let quotient = old_r / r;
+        (old_r, r) = (r, old_r - quotient * r);
+        (old_s, s) = (s, old_s - quotient * s);
+        (old_t, t) = (t, old_t - quotient * t);
+    }
+    (old_r, old_s, old_t)
+}
+/// Return the gcd.
+pub fn gcd(a: i64, b: i64) -> i64 {
+    extended_gcd(a, b).0
+}
+// Compute `n % abs(m)`
+fn modulo(n: i64, m: i64) -> i64 {
+    ((n % m) + m) % m
+}
+/// Return *x* such that (*xa*) mod *b* = 1.
+pub fn modinv(a: i64, b: i64) -> Result<i64, String> {
+    let (gcd, x, _) = extended_gcd(a, b);
+    if gcd == 1 {
+        Ok(modulo(x, b))
+    } else {
+        Err("Non-coprime generator error".to_string())
+    }
+}
+/// The rotation required from the current word to the
+/// lexicographically least mode of a word.
+/// Booth's algorithm requires at most 3*n* comparisons and *n* storage locations where *n* is the input word's length.
+/// See Booth, K. S. (1980). Lexicographically least circular substrings.
+/// Information Processing Letters, 10(4-5), 240–242. doi:10.1016/0020-0190(80)90149-0
+pub fn booth(scale: &[Letter]) -> usize {
+    let n = scale.len();
+    // `f` is the failure function of the least rotation; `usize::MAX` is used as a null value.
+    // null indicates that the failure function does not point backwards in the string.
+    // `usize::MAX` will behave the same way as -1 does, assuming wrapping unsigned addition
+    let mut f = vec![usize::MAX; 2 * n];
+    let mut k: usize = 0;
+    // `j` loops over `scale` twice.
+    for j in 1..2 * n {
+        let mut i = f[j - k - 1];
+        while i != usize::MAX && scale[j % n] != scale[k.wrapping_add(i).wrapping_add(1) % n] {
+            // (1) If the jth letter is less than s[(k + i + 1) % n] then change k to j - i - 1,
+            // in effect left-shifting the failure function and the input string.
+            // This appropriately compensates for the new, shorter least substring.
+            if scale[j % n] < scale[k.wrapping_add(i).wrapping_add(1) % n] {
+                k = j.wrapping_sub(i).wrapping_sub(1);
+            }
+            i = f[i];
+        }
+        if i == usize::MAX && scale[j % n] != scale[k.wrapping_add(i).wrapping_add(1) % n] {
+            // See note (1) above.
+            if scale[j % n] < scale[k.wrapping_add(i).wrapping_add(1) % n] {
+                k = j;
+            }
+            f[j - k] = usize::MAX;
+        } else {
+            f[j - k] = i.wrapping_add(1);
+        }
+        // The induction hypothesis is that
+        // at this point `f[0..j - k]` is the failure function of `s[k..(k+j)%n]`,
+        // and `k` is the lexicographically least subword of the letters scanned so far.
+    }
+    k
+}
+/// Rotate an array. Returns a Vec.
+pub fn rotate<T: std::clone::Clone>(slice: &[T], degree: usize) -> Vec<T> {
+    let degree = degree % slice.len();
+    if degree == 0 {
+        slice.to_vec()
+    } else {
+        [&slice[degree..slice.len()], &slice[0..degree]].concat()
+    }
+}
+/// The lexicographically least mode of a word (where the letters are in their usual order).
+pub fn least_mode(scale: &[Letter]) -> Vec<Letter> {
+    rotate(scale, booth(scale))
+}
+/// Delete all instances of one letter.
+pub fn delete(scale: &[Letter], letter: Letter) -> Vec<Letter> {
+    scale.iter().filter(|x| **x != letter).cloned().collect()
+}
+/// Letterwise substitution for scale words.
+///
+/// Note: This function does not fail even if the number of times `x` occurs in `template`
+/// does not divide `filler.len()`.
+pub fn subst(template: &[Letter], x: Letter, filler: &[Letter]) -> Vec<Letter> {
+    let mut ret = vec![];
+    let mut i: usize = 0;
+    if !filler.is_empty() {
+        for &letter in template {
+            if letter == x {
+                // Use the currently pointed-to letter of `filler` in place of `x`.
+                ret.push(filler[i % filler.len()]);
+                // Only update `i` when an `x` is replaced.
+                i += 1;
+            } else {
+                ret.push(letter);
+            }
+        }
+    } else {
+        // If `filler` is empty, we return `template` but with all `x`s removed.
+        return delete(template, x);
+    }
+    ret
+}
 /// Return the darkest mode of the MOS axby and the dark generator, using the Bresenham line algorithm.
 /// We chose the darkest mode rather than the brightest because this is the mode with brightness == 0.
-pub fn darkest_mos_mode_and_gen_bresenham(
+pub fn darkest_mos_mode_and_gen_bresenham(a: usize, b: usize) -> (Vec<Letter>, Vec<usize>) {
-    a: usize,
+     let d = gcd(a as i64, b as i64) as usize;
-    b: usize,
-) -> (Vec<Letter>, CountVector<Letter>) {
-     let d = gcd(a as u64, b as u64) as usize;
      if d == 1 {
          let count_gen_steps = modinv(a as i64, a as i64 + b as i64)
@@ Line 67: / Line 181: @@
          // Get the dark generator. We know how many steps and that this will give the perfect generator, not the
          // augmented one, since we just got the darkest mode.
-         let result_gen = CountVector::from_slice(&result_scale[0..count_gen_steps]);
+         let result_gen = {
+            let mut gen = vec![0, 0, 0];
+            for i in 0..count_gen_steps {
+                if result_scale[i] < 3 {
+                    gen[result_scale[i]] += 1;
+                }
+            }
+            gen
+        };
          (result_scale, result_gen)
      } else {
@@ Line 120: / Line 242: @@
      .concat();
      // Canonicalize every scale and remove duplicates
-     redundant_list
+     let mut canonicalized_list: Vec<_> = redundant_list
          .into_iter()
          .map(|scale| least_mode(&scale))
-         .sorted()
+         .collect();
-        .dedup()
+    canonicalized_list.sort();
-         .collect()
+    canonicalized_list.dedup();
+    canonicalized_list
+}
+fn main() {
+    for scale in mos_substitution_scales(&[5, 2, 4]) {
+         println!("{:?}", scale);
+    }
+    /*
+        [0, 0, 1, 2, 0, 2, 0, 1, 2, 0, 2]
+        [0, 0, 2, 0, 1, 2, 0, 0, 2, 1, 2]
+        [0, 0, 2, 0, 1, 2, 0, 2, 0, 1, 2]
+        [0, 0, 2, 0, 2, 1, 0, 2, 0, 1, 2]
+        [0, 0, 2, 0, 2, 1, 0, 2, 0, 2, 1]
+        [0, 0, 2, 1, 0, 2, 0, 0, 2, 1, 2]
+        [0, 0, 2, 1, 0, 2, 0, 1, 2, 0, 2]
+        [0, 0, 2, 1, 0, 2, 0, 2, 0, 1, 2]
+        [0, 0, 2, 1, 0, 2, 0, 2, 1, 0, 2]
+        [0, 1, 0, 2, 0, 2, 0, 1, 0, 2, 2]
+    */
 }
 </syntaxhighlight>