Macros

Due Friday, 26 Sep 1440 ET

Setup

Requirements

  • To complete this assignment, you must:
    • Create a 32 directory in your 271rs repository.
    • This folder must be a Cargo package.
    • It must leverage no other Cargo packages, namely it may not use packages for randomization.
    cargo new 32 --name macros --vcs none

My responsibility

  • I will provide a reference solution in Python
    • The reference will differ in the following ways:
      • They will not work on bits, as there isn’t great bit manipulation in Python without libraries.
      • I will provide an example of a left rotate while the assignment requires a right rotate.
  • I will provide a testing src/main.rs.
    • I will provide sample output.

Your responsibility

  • You will create a solution in Rust
    • It will contain 3 macros
      • choice
      • median
      • rotate - a “right” rotate.
        • You are advised, but not required, to make left rotate.

Summary

Description

  • The purpose of this homework is to write four (4) bitwise macros
    • Two trenanry operations
      • Choice
      • Median, also called Majority
    • And two rotations
      • Right, which sees use, and
      • Left, as an academic exercise
  • These will see use in the next assignment, SHA256
  • They are logically and historically interesting within cryptography
  • There is no graceful way, to my knowledge, to describe these on bits in Python
    • I will provide pseudo code over tuples of integers.
    • I provide conversion functions from strings.
    • I am aware of plenty non-graceful ways, but
      • If you want to show me one you like send me a DM

Macros

  • Rust macros are described in Rust Book 20.5
  • Basically, a macro replaces text in a .rs file before the code is compiled.
  • We will right max!
src/main.rs
let v: Vec<u32> = vec![1, 2, 3];
  • Suppose \(\exists\) the following in lib:
    • Do note - I wrote this multiline.
    • cargo fmt pushed it onto one line!
    src/lib.rs
    #[macro_export]
macro_rules! max {
  ( $x:expr, $y:expr ) => {
      if $x > $y { $x } else { $y }
  };
}

The #[macro_export] annotation indicates that this macro should be made available…

  • The body is match-like, but over text not computation.
    • There is only one case here: ( $x:expr, $y:expr )
    • This will be more complex than the cases you need.
  • Macro variables are $ prefixed, to differentiate from code variables.
    • You can accept a fixed number, like 2, as ( %x:expr, %y:expr )
    • Where:
      • $x and $y are variables that may be used within the macro body.
      • That match to Rust expressions (like val or 7+2) via :expr
  • We can then use the macro:
src/main.rs
fn main() {
    dbg!(package_name_likely_macros::max!(1, 2));
    dbg!(package_name_likely_macros::max!(2, 1));
}
  • We see the expected result… but how?
$ cargo r
   Compiling hamming v0.1.0 (/home/user/tmp/scratch)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.22s
     Running `target/debug/hamming`
[src/main.rs:2:5] package_name_likely_macros::max!(1, 2) = 2
[src/main.rs:3:5] package_name_likely_macros::max!(2, 1) = 2

Internals

  • rustc comes along and sees max!
  • rustc looks into package_name_likely_macros and looks for src/lib.rs
  • rustc looks for macro_rules! max
  • rustc matches the pattern ( $x:expr, $y:expr ) to (1, 2)
    • As 1 and 2 are valid Rust expressions.
  • rustc replaces max!(1,2) with if $x > $y { $x } else { $y }
  • rustc replaces $x with 1 and $y with 2
  • Then, at long last, rustc compiles the code and creates an executable.

Quick Exercises

Sizeof

  • You will notice something very annoying soon, if not already.
  • You probably don’t know how big any thing is in a macro!
    • They don’t follow the Rust convention of everything having a type!
    • That’s why you can println! or dbg! or vec! any type!
  • You just may need to know how many bits are in what you’re working with:
fn main() {
    dbg!(size_of_val(&1));
}
  • Read more
  • This gives size in bytes, not bits, but just may come in handy!
  • In a future assignment, you will be working on u64.
$ cat src/main.rs
fn main() {
    dbg!(size_of_val(&1_u64));
}
$ cargo run
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/hamming`
[src/main.rs:2:5] size_of_val(&1_u64) = 8
  • We must & prefix to allow the function to work on borrowed values, when checking the size of e.g. vectors.

Choice

  • Here I provide Pythonic boolean choice and bitwise choice.
  • You will need Rust bitwise choice.
  • Choice is sometimes also referred to as the “ternary operator”
    • Most famously in .js
    • This is… potentially confusing.
    • It is a ternary operator.
    • The Python operator is non-standard and intentionally ugly.
macros.py
# ref: choice := (e and f) xor ((not e) and g)
# src: https://en.wikipedia.org/wiki/SHA-2

# We just tell Python the ints are bools
# We just use "!=" as xor

def _choice(e:bool, f:bool, g:bool) -> bool:
    return int(f if e else g)
    # return int((e and f) != ((not e) and g))

import itertools

tester = list(itertools.product([0, 1],repeat=3))

print(" === Boolean Choice === ")
[print('_choice'+str(test), '->', _choice(*test)) for test in tester]

arrays = (tuple(zip(*tester)))

def choice(e:tuple[bool], f:tuple[bool], g:tuple[bool]) -> tuple[bool]:
    return tuple(_choice(_e, _f, _g) for _e, _f, _g in zip(e,f,g))

# This was ugly
# print('choice'+str(arrays), '->', choice(*arrays))

# pretty print
bitstr = lambda bits : "".join([str(b) for b in bits])
bsstrs = lambda arrs : str(tuple(bitstr(bits) for bits in arrs))
print(" === Bitwise Choice === ")
print('choice'+bsstrs(arrays), '->', "'"+bitstr(choice(*arrays))+"'")
  • You can run it yourself, but here is the output for reference.

Median

Or “Majority”

  • Here I provide Pythonic boolean median and bitwise median.
  • You will need Rust bitwise median.
  • I will take it as given you know what a median and majority are.
    • Logicially equivalent with \(n = 3\)
  • The following code is appended to “macros.py”
macros.py
import numpy as np

def _median(e:bool, f:bool, g:bool) -> bool:
    return int(np.median([e,f,g]))

print(" === Boolean Median === ")
[print('_median'+str(test), '->', _median(*test)) for test in tester]

def median(e:tuple[bool], f:tuple[bool], g:tuple[bool]) -> tuple[bool]:
    return tuple(_median(_e, _f, _g) for _e, _f, _g in zip(e,f,g))

print(" === Bitwise Median === ")
print('median'+bsstrs(arrays), '->', "'"+bitstr(median(*arrays))+"'")
  • You can run it yourself, but here is the output for reference.

Rotate

Sometimes “Rotright and Rotleft”

  • Virtually identical to rotation ciphers.
  • We understand this as:
    • Take an array and,
    • Take a numerical value…
      • of less than the length of the array.
    • Maintain all elements of the array, but
      • Increase their index by the numerical value, and
      • Indices greater than array length wrap around…
        • Using modulo array length.
  • We apply this same idea to the notion of boolean arrays.
    • A unsigned int is a boolean array of some length.
    • It is possible to determine these lengths.
  • Here is a Python rotleft on boolean arrays of size 8.
macros.py
def rotleft(a:tuple[bool], n:int) -> tuple[bool]:
    return a[n:] + a[:n]

print(" === Bitwise Rotleft === ")
array = (0,0,1,0,1,1,0,1)
for n in range(len(arrays[0])+1):
    print('rotleft('+bitstr(array)+','+str(n)+') ->', bitstr(rotate(array,n)))
  • You can run it yourself, but here is the output for reference.
  • We note that this forms a “backward” or “leftward” rotate.
    • This is a non-standard rotate, often called lotate or rotleft
    • A future assignment will use a “forward” or “rightward” rotate.
  • Without showing code, it would look like this.

Overflow

  • Rust appears to implement some shifting operations a bit differently that other languages.
  • Read this
  • Look at this:
($x.checked_shr($y).unwrap_or(0))
  • That r in shr is for right.

Tester

src/main.rs
fn main() {
    /* Various Variables*/
    let a : [u64; 4] = [0x1111111111110000, 0x1111000011001100, 0x1100110010101010, 0x0123456789ABCDEF];

    println!("*Rotates use a decimal shift value, but print in hexadecimal:\n");
    println!("choice(\n{:016X},\n{:016X},\n{:016X}) = \n--------\n{:016X}\n\n", a[0], a[1], a[2], macros::choice!(a[0], a[1], a[2]));
    println!("median(\n{:016X},\n{:016X},\n{:016X}) = \n--------\n{:016X}\n\n", a[0], a[1], a[2], macros::median!(a[0], a[1], a[2]));
    println!("*Rotates use a decimal shift value, but print in hexadecimal:\n");
    println!("rotate!(\n{:016X}, 04) = \n--------\n{:016X}\n\n", a[3],   macros::rotate!(a[3], 4));
    println!("rotate!(\n{:016X}, 08) = \n--------\n{:016X}\n\n", a[3],   macros::rotate!(a[3], 8));
    println!("rotate!(\n{:016X}, 12) = \n--------\n{:016X}\n\n", a[3],   macros::rotate!(a[3], 12));
    println!("rotate!(\n{:016X}, 02) = \n--------\n{:016X}\n\n", 0x1000, macros::rotate!(0x1000_u64, 2));
    println!("rotate!(\n{:016X}, 30) = \n--------\n{:016X}\n\n", 0x1000, macros::rotate!(0x1000_u64, 30));
}
  • Sample output: