Macros

HW 0x1: Due Th, Jan 30

Review 

Goal: Think about C variables as bits

  • My responsibility
    • I will provide a reference solution in Python
    • I will provide an autograder Containerfile
  • Your responsibility
    • You will create a solution in C as an “macros.c” file
    • You will create a private GitHub repository named “crypto”
    • You will create a folder in this repository named “macros”
    • You will store your “macros.c” file in the “macros” folder.
    • You will add me as a collaborator through the GitHub web application
        • My GitHub account cd-public is attached to my @wu address.
    • If you would like to fork an existing repository, use this one:

Topic Areas

Review: Newish:
- bits - Macros
- bytes - Sizeof
- operators

Podman 

Setup

  • For this lab, I used the following Containerfile
    • Same as lecture
    • I didn’t even rename it
Containerfile
  • I could build with the following, but I already had it built:
  • I conducted the full hw within a single container’s vim instance.

GitHub 

Read this in GitHub Docs

Inviting collaborators to a personal repository

You can add unlimited collaborators on public and private repositories.

About collaboration in a personal repository

To collaborate with users in a repository that belongs to your personal account on GitHub, you can invite the users as collaborators.

If you want to grant more granular access to the repository, you can create a repository within an organization. For more information, see Access permissions on GitHub.

Inviting a collaborator to a personal repository

You can send an invitation to collaborate in your repository directly to someone on GitHub, or to the person’s email address..

GitHub limits the number of people who can be invited to a repository within a 24-hour period. If you exceed this limit, either wait 24 hours or create an organization to collaborate with more people. For more information, see Creating a new organization from scratch.

  1. Ask for the username of the person you’re inviting as a collaborator. If they don’t have a username yet, they can sign up for GitHub. For more information, see Creating an account on GitHub.{1. On GitHub, navigate to the main page of the repository.
  2. Under your repository name, click Settings. If you cannot see the “Settings” tab, select the dropdown menu, then click Settings.
  3. In the “Access” section of the sidebar, click Collaborators.
  4. Click Add people.
  5. In the search field, start typing the name of person you want to invite, then click a name in the list of matches.
  6. Click Add NAME to REPOSITORY.
  7. The user will receive an email inviting them to the repository. Once they accept your invitation, they will have collaborator access to your repository.

Sketch 

  • 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
  • For this homework, you will need some form of bit printing
    • If your printb from lab is struggling, use %b in debug
    • Just remove it before your turn in your work.
  • We next introduce macros.

Macros 

  • The purpose of this homework is to write four (4) bitwise macros.
  • C macros exist in the “preproprocessor”.
  • Here is an example of preprocessor directive you have written already:
#include <stdio.h>
  • You probably also have used a define directive
#define ABCS "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  • The define directive is used to define something called a macro.
    • When used to define constants, those are just macros that return a value.
  • We can also define macros that accept arguments, the most famous are MIN and MAX
    • I grabbed these from OpenBSD
    • They have fallen out of favor for a complicated reason.
    • In general, use functions.
    • We use macros to learn about them, not to learn to write them.
/* Macros for min/max. */
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
  • I’d encourage you to play around a bit with these macros.
    • You don’t need to fully understand before diving into choice, median, rotate.
    • But a little background can help.
int x = 50;
int a = 'a';
printf("%d\n", MAX(x++,a++))
  • In general, you want to use a lot of parens in macros.
    • Try some things out to try to see why.

Choice Show

  • Here I provide Pythonic boolean choice and bitwise choice, and C boolean choice.
  • You will need C 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.
  • The following defines a macro for boolean choice.
    • Though not particularly gracefully.
/* Macro for boolean choice. */
#define CHOICE(e,f,g) ((e)?(f):(g))
  • Update the macro to perform bitwise choice.
    • It should be a single line macro.
    • It should use bitwise operators.

Median Show

  • Here I provide Pythonic boolean median and bitwise median, and C boolean median.
  • You will need C bitwise median.
  • I will take it as given you know what a median is.
  • 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.
  • The following defines a macro for boolean median.
    • Though not particularly gracefully.
    • C !! is very close to Python bool()
/* Macro for boolean median. */
#define MEDIAN(e,f,g) ((!!(e) + !!(f) + !!(g)) > 1)
  • Update the macro to perform bitwise median.
    • It should be a single line macro.
    • It should use bitwise operators.

Sizeof 

  • You may have noticed something while writing printb:
    • That not know how many bits you had was annoying.
  • Not to worry, C can help us.
    • A char is always exactly 8 bits
      • This is also called one byte
      • It is trivial to verifying this experimentally.
    • Everything else is some multiple of char
    • To find how many char’s big something is, use sizeof
  • I compile with -w to silence an error.
    • sizeof doesn’t run an integer, so we shouldn’t print with %d
    • More latter.
$ cat sizeof.c
#include <stdio.h>

int main() {
        char c = 1;
        int n = 2;
        char s[8] = {1,2,3,4,5,6,7,8};
        printf("sizeof(c) = %d, sizeof(n) = %d, sizeof(s) = %d\n",
                        sizeof(c),
                        sizeof(n),
                        sizeof(s)
              );
        return 0;
}
$ gcc sizeof.c -w
$ ./a.out
sizeof(c) = 1, sizeof(n) = 4, sizeof(s) = 8
  • To make introducing rotate easier, all examples will be on char
  • Rotate is used in cryptography on things 32 bits in size.
    • Usually an int is this big, but not always.
    • There’s ways to manage this.
  • I will test your rotate code on the unsigned int type, which is usually 32 bits in size.
    • You can assume 32, for now.

Rotate 

  • We recall cipher rotation.
  • 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 bitwise rotate 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.

Note:

  • The C language bitwise operations often seem quite unstable.
    • It is a virtual certainty you will encounter pernicious bugs.
    • Use unsigned int or just unsigned to avoid negative shenanigans.
    • Print everything all the time.
    • Liberally consult printf and C language documentation
    • Ask questions early and often.

Reference implementation

  • Your task is to use bitwise operators to write a rotate macro
  • To test your code, here is a function using something called “assembly”.
  • See the enrichment lecture to learn more.
  • This should work as a drop-in reference implementation.
    • It is the implementation used by the autograder.
unsigned rotate(unsigned val, unsigned amt) {
        asm("rorl %%cl, %0" : "+r" (val) : "c" (amt));
        return val;
}