BigAdd

Lab 0x5

Review 

Goal: Learn modular and mixed precision arithmetic.

Review: Newish:
- stdint - headers
- modulo
- rings
  • There are no required exercises of this lab.
  • It is supplementary material to the 4096_t homework.
    • 4096_t requires add, sub, mul, div
    • This lab provides sub
    • This lab introduces add

Podman 

Setup

  • For this lab, I used the following Containerfile
    • Same as the printb lab
Containerfile
  • I built via the following:
  • I conducted the full lab within a single container’s vim instance.
  • I conducted all work within this vim window and it’s :term

Header 

Python 

2 ⇒ 3

  • Python 2 had maximum integer sizes, not unlike C
  • Python 3 lacks such limitations.
  • While unsuitable for cryptographic applications for limitations including performance, it is suitable for testing.
  • It is a simple enough matter to translate the following into Python:
4096_t.c
int main() {
    uint64_t min[S], sub[S], dif[S];
    size_t i;
    memset(min, 0, BYTES);
    memset(sub, 0, BYTES);
    for (i = 0; i < S; i++) {
        min[i] = i * 3;
        sub[i] = i * 2;
    }
    bigsub(min, sub, dif);
    for (i = 0; i < S; i++) {
        printf("dif[%02lx] = %02lx\n", i, dif[i]);
    }
    return 0;
}
  • Simply:
    • Create two accumulating variables.
    • Add in values multiplied by powers of two.
    • Perform the built-in Python subtract
    • Print the output as a hex value, perhaps split onto multiple lines.
S = 64

min, sub = 0, 0
# Factor this, obviously.
[min := min + 3 * n * (2 ** (n * 64)) for n in range(S)]
[sub := sub + 2 * n * (2 ** (n * 64)) for n in range(S)]
print(hex(min-sub))

Recommendation

  • It is recommended but not required to develop an interface between Python and your 4096_t.
    • I recommend passing numerical values as hexadecimal strings.
    • Generate values in Python, perform operations, and test results vs. 4096_t
  • I found it difficult to debug bigadd and bigsub without constructing an interface.
  • Here is an example of a function I used in testing:
/* print the big value as a string */
void seebig(uint64_t *a) {
    size_t i;
    for (i = S-1; i < S ; i--) {
        fprintf(stderr, "%016lx ", a[i]); 
        if ((i % 8 == 0 && i)) {
            fprintf(stderr, "\n");
        }       
    }
    fprintf(stderr, "\n\n");
    return;
}

Autograder

  • The interface implemented by the autograder may be informative here.
    • It uses a Python script.
    • It uses a dedicated .c file with a main function.
    • It uses gcc 4096_t.c tester.c to compile the 4096_t code for use in the tester executable.
    • It uses Python subprocess to examine the results.
  • I was unable to achieve a bugfree multiply absent this interface, but was able to progress rapidly once I developed it.

BigAdd 

Big Addition

  • Using what you know so far, write bigadd.
    • Declare bigadd in the header file.
    • Define bigadd in the .c file.
    • Test bigadd to ensure, mostly, you are handling carries correctly.
4096_t.h
/* 4096_t.h */

#ifndef _4096_T_H
#define _4096_T_H

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define BYTES 4096 / 8 
#define S BYTES / sizeof(uint64_t)

/* Given a
 * minuend    uint64_t min[S]
 * subtrahend uint64_t sub[S]
 * difference uint64_t dif[S]
 * 1. Populate dif with the difference between min and sub
 * 2. Return the "carry bit" capturing whether an overflow occured.
  */
uint64_t bigsub(uint64_t *min, uint64_t *sub, uint64_t *dif); 

/* Given a
 * addend_0     uint64_t in0[S]
 * addend_1     uint64_t in1[S]
 * sum          uint64_t sum[S]
 * 1. Populate sum with the sum over in0 and in1
 * 2. Return the "carry bit" capturing whether an overflow occured.
  */
uint64_t bigadd(uint64_t *in0, uint64_t *in1, uint64_t *sum); 

#endif /* _4096_T_H */
  • If you want different names for the inputs, use “augend” and “addend”.
  • Addition is generally regarded associative (order doesn’t matter), but
  • There are times in computing that operand order matters.
    • In x86 assembly, add accepts two operands, storing the result in the first (augend) operand’s location.
  • It would be suitable to write all bigops in this format, if that is your perference!
    • Just different.

Testing

  • You should minimally be able to do the following, over arbitrary data.
    • Check the carries just in case, of course.
    • Or use an e.g. biggte to determine which value is greater than or equal before subtracting.
4096_t.c
int main() {
    uint64_t a[S], b[S], c[S], d[S];
    size_t i;
    memset(a, 0, BYTES);
    memset(b, 0, BYTES);
    for (i = 0; i < S; i++) {
        min[i] = i * 3;
        sub[i] = i * 2;
    }
    bigsub(a, b, c);
    bigadd(b, c, d);
    /* You may have written `bigeqs` or */
    for (i = 0; i < S; i++) {
        if (a[i] != d[i]) {
            return 1;
        }
    }
    return 0;
}