diff options
80 files changed, 4532 insertions, 7 deletions
diff --git a/2/3_int_arith/212.c b/2/3_int_arith/212.c new file mode 100644 index 0000000..e746216 --- /dev/null +++ b/2/3_int_arith/212.c @@ -0,0 +1,36 @@ +#include <stdio.h> + +int bis(int x, int m) { + return x | m; +} +int bic(int x, int m) { + return x & ~m; +} +int bool_or(int x, int y) { + int result = bis(x, y); + return result; +} +int bool_xor(int x, int y) { + int result = bis(bic(x, y), bic(y, x)); + return result; +} +int bool_eq(int x, int y) { + int result = !(x^y); + return result; +} + +void main() { + printf("=== 2.11 ===\n"); + int x = 0x87654321; + printf("%x\n", x & 0xFF); + printf("%x\n", ~x ^ 0xFF); + printf("%x\n", x | 0xFF); + + printf("=== 2.12 ===\n"); + printf("%x\n", bool_or(1, 1)); + printf("%x\n", bool_xor(1, 1)); + + printf("=== 2.15 ===\n"); + printf("%x\n", bool_eq(0x87654321, 0x87654321)); + printf("%x\n", bool_eq(14, 13)); +} diff --git a/2/3_int_arith/225.c b/2/3_int_arith/225.c new file mode 100644 index 0000000..51f1937 --- /dev/null +++ b/2/3_int_arith/225.c @@ -0,0 +1,20 @@ +#include <stdio.h> +#include <limits.h> + +float sum_elements(float a[], unsigned length) { + int i; + float result = 0; + + for (i = 0; i <= length-1; i++) { + printf("iter\n"); + result += a[i]; + } + return result; +} + +void main() { + printf("hi\n"); + float ele[] = {1.0, 2.0}; + // sum_elements(ele, 0); + printf("%d", INT_MAX+1); +} diff --git a/2/3_int_arith/227.c b/2/3_int_arith/227.c new file mode 100644 index 0000000..cc22cf9 --- /dev/null +++ b/2/3_int_arith/227.c @@ -0,0 +1,20 @@ +#include <stdio.h> +#include <limits.h> + +// with limits.h +int uadd_ok(unsigned x, unsigned y) { + printf("x: %u, y: %u\n", x, y); + return x <= (UINT_MAX - y); +} + +// without limits.h +int uadd_ok_without(unsigned x, unsigned y) { + unsigned sum = x + y; + return sum >= x; +} + +void main() { + printf("%u\n", UINT_MAX); + printf("%d\n", uadd_ok(10, 20)); + printf("%d", uadd_ok(UINT_MAX / 2, UINT_MAX / 2)); +} diff --git a/2/3_int_arith/230.c b/2/3_int_arith/230.c new file mode 100644 index 0000000..8bba282 --- /dev/null +++ b/2/3_int_arith/230.c @@ -0,0 +1,25 @@ +#include <limits.h> +#include <stdio.h> + +int tadd_ok(int x, int y) { + int positive_overflow = x > 0 && y > 0 && x + y < 0; + int negative_overflow = x < 0 && y < 0 && x + y >= 0; + return !positive_overflow && !negative_overflow; +} + +int tadd_buggy(int x, int y) { + int sum = x+y; + printf("sum: %d, sum-x: %d, sum-y: %d", sum, sum-x, sum-y); + return (sum-x == y) && (sum-y == x); +} + +/* buggy */ +int tsub_ok(int x, int y) { + return tadd_ok(x, -y); +} + +void main() { + printf("INT_MIN: %d, %d\n", -(INT_MIN), INT_MIN); + printf("result: %d\n", tadd_ok(10, 100)); + printf("result2: %d", tadd_buggy(INT_MAX, 1)); // The sum is a very negative number, when we take the difference with it's parts it just does a negative overflow to get the original parts back. +} diff --git a/2/3_int_arith/236.c b/2/3_int_arith/236.c new file mode 100644 index 0000000..b05da34 --- /dev/null +++ b/2/3_int_arith/236.c @@ -0,0 +1,19 @@ +#include <stdio.h> +#include <stdint.h> +#include <inttypes.h> + +int tmult_ok(int x, int y) { + int64_t upcasted_result = (int64_t) x * y; + return upcasted_result == (int) upcasted_result; +} + +void main() { + int m = 1<<31; + int n = 1<<31; + printf("%" PRId64 "\n", (int64_t) (m * n)); + printf("%d\n", tmult_ok(m, n)); + printf("%d\n", tmult_ok(10, 20)); + printf("%d\n", tmult_ok(10, 20)); +} + + diff --git a/2/3_int_arith/242.c b/2/3_int_arith/242.c new file mode 100644 index 0000000..07634e3 --- /dev/null +++ b/2/3_int_arith/242.c @@ -0,0 +1,14 @@ +#include <stdio.h> + +int div16(int x) { + // my inefficient method that just checks the sign bit: int sign_bit = (unsigned) (x & 1<<31) >> 31; + int bias = (x >> 31) & 0xF; + return (x + bias)>>4; +} + +void main() { + int result = div16(-17); + printf("%d\n", result); + result = div16(17); + printf("%d\n", result); +} diff --git a/2/3_int_arith/243.c b/2/3_int_arith/243.c new file mode 100644 index 0000000..9a60eda --- /dev/null +++ b/2/3_int_arith/243.c @@ -0,0 +1,22 @@ +// #define M +// #define K +// int arith(int x, int y) { +// int result = 0; +// result = x*M + y/N; +// return result; +// } +// +// int optarith(int x, int y) { +// int t = x; +// x <<= 5; +// x -= t; +// if (y < 0) y += 7; +// y >>= 3; +// return x+y; +// } +#include <stdio.h> + +int main() { + int x = 3; + printf("%d", x<<1); +} diff --git a/2/3_int_arith/check b/2/3_int_arith/check Binary files differnew file mode 100755 index 0000000..f50a240 --- /dev/null +++ b/2/3_int_arith/check diff --git a/2/3_int_arith/check-211.c b/2/3_int_arith/check-211.c new file mode 100644 index 0000000..174b0f4 --- /dev/null +++ b/2/3_int_arith/check-211.c @@ -0,0 +1,27 @@ +#include <stdio.h> + +void inplace_swap(int *x, int *y) { + *y = *x ^ *y; + *x = *x ^ *y; + *y = *x ^ *y; +} + +void reverse_array(int a[], int cnt) { + int first, last; + for (first = 0, last = cnt-1; + first < last; + first++,last--) + inplace_swap(&a[first], &a[last]); +} + +void print_array(int a[], int len) { + int i; + for (i = 0; i < len; i++) + printf("%d", a[i]); +} + +void main() { + int a[] = {1,2,3,4,5, 6}; + reverse_array(a, 6); + print_array(a, 6); +} diff --git a/2/3_int_arith/show-bytes.c b/2/3_int_arith/show-bytes.c new file mode 100644 index 0000000..0860b8d --- /dev/null +++ b/2/3_int_arith/show-bytes.c @@ -0,0 +1,33 @@ +#include <stdio.h> + +typedef unsigned char *byte_pointer; + +void show_bytes(byte_pointer start, size_t len) { + int i; + for (i = 0; i < len; i++) + printf(" %.2x", start[i]); + printf("\n"); +} + +void show_int(int x) { + show_bytes((byte_pointer) &x, sizeof(int)); +} + + +void show_float(float x) { + show_bytes((byte_pointer) &x, sizeof(float)); +} + + +void show_pointer(void *x) { + show_bytes((byte_pointer) &x, sizeof(void *)); +} + +void test_show_bytes(int val) { + int ival = val; + float fval = (float) ival; + int *pval = &ival; + show_int(ival); + show_float(fval); + show_pointer(pval); +} diff --git a/2/3_int_arith/xdr.c b/2/3_int_arith/xdr.c new file mode 100644 index 0000000..63d4b24 --- /dev/null +++ b/2/3_int_arith/xdr.c @@ -0,0 +1,28 @@ +#include <stdio.h> +#include <stddef.h> +#include <stdlib.h> +#include <string.h> +#include <stdint.h> + +void* copy_elements(void* ele_src[], int ele_cnt, size_t ele_size) { + uint64_t asize = ele_cnt * (uint64_t) ele_size; + void *result = malloc(asize); + if (result == NULL) + return NULL; + void *next = result; + int i; + for (i = 0; i < ele_cnt; i++) { + memcpy(next, ele_src[i], ele_size); + next += ele_size; + } + return result; +} + +void main() { + int i = 0; + char* input[] = {"somestring","some666666"}; + printf("%s\n", input[0]); + printf("%s\n", *(input+1)); // these two lines are basically the same thing *(input+1) = input[1] + char* result = copy_elements((void *) input, 2, 10); + printf("%s\n", result); +} diff --git a/2/4_floating_point/51.ora b/2/4_floating_point/51.ora Binary files differnew file mode 100644 index 0000000..f39bc3f --- /dev/null +++ b/2/4_floating_point/51.ora diff --git a/2/4_floating_point/special_values.c b/2/4_floating_point/special_values.c new file mode 100644 index 0000000..cedd2ba --- /dev/null +++ b/2/4_floating_point/special_values.c @@ -0,0 +1,39 @@ +#include <stdio.h> + +#define POS_INFINITY 1.8e400 +#define NEG_INFINITY -POS_INFINITY +#define NEG_ZERO (-1.0/POS_INFINITY) + +int main() { + /* + 2.53 + */ + printf("%f\n", POS_INFINITY); + printf("%f\n", NEG_INFINITY); + printf("%f\n", NEG_ZERO); + + /* + 2.54 + A. Yes, int->double->int, int->double preserves value, so double->int after that also has the same value, since we know rounding and overflow is not relevant. + B. NO, same as A, actually Fmax < Tmax, so casting from int to float can overflow. + C. No, double->float->double, float has lower range, so overflow could happen. Float also has lower precision, so when converting to float there may also be round-to-even. + D. Yes, float->double->float, exact value can be kept when casting to double. + E. Yes, Sign bit can be flipped without influencing the rest of the bit pattern. So the double negation cancels itself and the value is exactly the same after. + F. Yes, 1.0/2 == 1/2.0, integers are first cast to float. + G. Yes, d*d >= 0.0, this is a result of the monotonicity property of floating point numbers. + H. (f+d)-f == d, in the addition rounding errors can occur, for example when adding a small value to a large value. It can also overflow, causing (inf-f) = inf. + In this comparison the problem arises when the value that is compared is the small one, since that will get lost in the rounding error of the addition. + */ + int x = (1<<31) - 1; + float f = 3.14f; + double d = 1e307f; + printf("%d\n", x == (int) (double) x); + printf("%d\n", x == (int) (float) x); + printf("%d, value: %f\n", d == (double) (float) d, (double) (float) d); + printf("%d, value: %f, orig: %f\n", f == (float) (double) f, (float) (double) f, f); + printf("%d\n", f == -(-f)); + printf("%d\n", 1.0/2 == 1/2.0); + printf("%d\n", d * d >= 0.0); + printf("%d\n", (f+d)-f == d); + return 0; +} diff --git a/2/homework/2.59.c b/2/homework/2.59.c new file mode 100644 index 0000000..06e2f39 --- /dev/null +++ b/2/homework/2.59.c @@ -0,0 +1,186 @@ +#include <stdio.h> +#include <limits.h> + +typedef unsigned char *byte_pointer; + +void show_bytes(byte_pointer start, size_t len) { + int i; + for (i = 0; i < len; i++) { + printf(" %.2x", start[i]); + } + printf("\n"); +} + +void show_int(int x) { + show_bytes((byte_pointer) &x, sizeof(int)); +} + +void show_float(float x) { + show_bytes((byte_pointer) &x, sizeof(float)); +} + +void show_pointer(void *x) { + show_bytes((byte_pointer) &x, sizeof(void *)); +} + +void test_show_bytes(int val) { + int ival = val; + float fval = (float) val; + int *pval = &ival; + show_int(ival); + show_float(fval); + show_pointer(pval); +} + +int is_little_endian() { + int val = 1; + byte_pointer pval = (byte_pointer) &val; + return *pval == 1; +} + +unsigned int combine_least_significant_with_remaining(unsigned int x, unsigned int y) { + return (x & 0xFF) | (y & ~0xFF); +} + +unsigned replace_byte(unsigned x, int i, unsigned char b) { + unsigned remover = ~(0xFF<<(i<<3)); + unsigned adder = b<<(i<<3); + return (x & remover | adder); +} + +int bit_any_one(int x, int mask, int rshift) { + return (((x >> rshift) & ~0) & mask) && 1 || 0; +} + +int bit_any_zero(int x, int mask, int rshift) { + return (((x >> rshift) ^ ~0) & mask) && 1 || 0; +} + +int int_shifts_are_arithmetic() { + int ones_or_zeroes = ~0; + int rshifted = ones_or_zeroes >> 1; + return (rshifted >> (sizeof(int) - 1)) & 1; +} + +const int w = sizeof(int)*8; +unsigned srl(unsigned x, int k) { + /* Perform shift arithmetically */ + unsigned xsra = (int) x >> k; + unsigned ones_or_zeroes = ~0; + unsigned shiftl_minus_one = ones_or_zeroes<<(w-1 - k); + unsigned shiftl = shiftl_minus_one + shiftl_minus_one; + unsigned mask = ~shiftl; + printf("value: "); + show_int(x); + printf("mask: "); + show_int(mask); + return xsra & mask; +} + +int sra(int x, int k) { + /* Perform shift logically */ + int xsrl = (unsigned) x >> k; + int has_msb = ((1<<(w - 1)) & x) && 1; + unsigned ones_or_zeroes = (!has_msb) - 1; + unsigned shiftl_minus_one = ones_or_zeroes<<(w-1 - k); + unsigned shiftl = shiftl_minus_one + shiftl_minus_one; + unsigned mask = shiftl; + printf("value: "); + show_int(x); + printf("mask: "); + show_int(mask); + return xsrl | mask; +} + +void test_srl() { + printf("===== SRL\n"); + printf("zero shifts, INT_MIN, -1, 0, INT_MAX\n"); + show_int(srl(INT_MIN, 0)); + show_int(srl(-1, 0)); + show_int(srl(0, 0)); + show_int(srl(INT_MAX, 0)); + printf("16 bit shift, INT_MIN, -1, 0, INT_MAX\n"); + show_int(srl(INT_MIN, 16)); + show_int(srl(-1, 16)); + show_int(srl(0, 16)); + show_int(srl(INT_MAX, 16)); +} + +void test_sra() { + printf("===== SRA\n"); + printf("zero shifts, INT_MIN, -1, 0, INT_MAX\n"); + show_int(sra(INT_MIN, 0)); + show_int(sra(-1, 0)); + show_int(sra(0, 0)); + show_int(sra(INT_MAX, 0)); + printf("16 bit shift, INT_MIN, -1, 0, INT_MAX\n"); + show_int(sra(INT_MIN, 16)); + show_int(sra(-1, 16)); + show_int(sra(0, 16)); + show_int(sra(INT_MAX, 16)); +} + +int any_odd_one(unsigned x) { + return (x & 0xAAAAAAAA) && 1; +} + +int odd_ones(unsigned x) { + /* + I cheated by looking at other people's answers online for this one after a couple of hours. + I somehow got stuck on the idea that I should use the previous excercise's mask for odd numbers (Guess I was tired kappa). + + The solution is kind of clever (But requires some C experience imo). It uses the fact that XOR is zero if you have two ones. + And it kind of subtracts those two ones from the total ones until you have either 0 or 1 left. + + It is done by recursively taking two halves and crossing off or keeping ones in the halves. + Until the halve is just a 1-bitvector containing the parity bit. + */ + x ^= x>>16; + x ^= x>>8; + x ^= x>>4; + x ^= x>>2; + x ^= x>>1; + return x & 0x01; +} + +int main() { + printf("odd_ones: %d\n", odd_ones(0b11)); + + // 64 + printf("any_odd_one: %d\n", any_odd_one(5)); + return 0; + + // 63 + printf("================ 63 ================\n"); + test_srl(); + test_sra(); + return 0; + // 62 + printf("================ 62 ================\n"); + printf("%d\n", int_shifts_are_arithmetic()); + + // 61 + printf("================ 61 ================\n"); + int shift = (sizeof(int) - 1) << 3; + printf("%d\n", bit_any_one(INT_MIN, 0xFF, shift)); + printf("%d\n", bit_any_one(256, 0xFF, 0)); + printf("%d\n", bit_any_one(1, 0xFF, 0)); + printf("%d\n", bit_any_zero(-1, 0xFF, 0)); + + // 60 + printf("================ 60 ================\n"); + printf("%x\n", replace_byte(0x12345678, 2, 0xAB)); + printf("%x\n", replace_byte(0x12345678, 0, 0xAB)); + + // 59 + unsigned int combined = combine_least_significant_with_remaining(0x89ABCDEF, 0x76543210); + show_bytes((byte_pointer) &combined, sizeof(unsigned int)); + + // 58 + show_int(1); + printf("is little endian: %d\n", is_little_endian()); + + return 0; + // 55-57 + test_show_bytes(13); +} diff --git a/2/homework/2.66.c b/2/homework/2.66.c new file mode 100644 index 0000000..1a912f1 --- /dev/null +++ b/2/homework/2.66.c @@ -0,0 +1,134 @@ +#include <stdio.h> + +typedef unsigned char *byte_pointer; + +int is_little_endian() { + int val = 1; + byte_pointer pval = (byte_pointer) &val; + return *pval == 1; +} + +/* + Generate mask indicating leftmost 1 in x. Assume w=32 + For example, 0xFF00 -> 0x8000, and 0x6600 --> 0x4000 + + |, &, ^, >>, << + +, - + &&, || + + 0110 0110 0000 0000 + .... + 0110 0110 0110 0110 + | + 0000 0110 0110 0110 + | + 0001 1001 1001 1001 + = + 0111 1111 1111 1111 + ~ + 1000 0000 0000 0000 + >>1 + 0100 0000 0000 0000 + + 0001 0000 0000 0000 + |>>8 + 0001 0000 0001 0000 + |>>4 + 0001 0001 0001 0001 + |>>2 + 0001 0101 0101 0101 + |>>1 + 0001 1111 1111 1111 + + */ +int leftmost_one(unsigned x) { + x |= x>>16; + x |= x>>8; + x |= x>>4; + x |= x>>2; + x |= x>>1; + return x & ~(x>>1); +} + +int bad_int_size_is_32() { + /* Set most significant bit (msb) of 32-bit machine */ + int set_msb = 1 << 15; + set_msb = set_msb << 15; + set_msb = set_msb << 1; + + /* Shift past msb of 32-bit word ?? A. undefined behavior if you shift more than the data type*/ + int beyond_msb = set_msb + set_msb; /* should overflow to zero if on 32 bit machine */ + + /* + set_msb is nonzero when word size >= 32 + beyond_msb is zero when word size <= 32 + */ + return set_msb && !beyond_msb; +} + +/* + Mask with least significant n bits set to 1 + Examples: n = 6 --> 0x3F, n = 17 --> 0x1FFFF + Assume 1 <= n <= w + */ +int lower_one_mask(int n) { + return ((unsigned) ~0)>>(32-n); +} + +/* + Do a rotating left shift. Assume 0 <= n < w + Examples when x = 0x12345678 and w = 32: + n=4 -> 0x23456781, n=20 -> 0x67812345 + */ +unsigned rotate_left(unsigned x, int n) { + unsigned left_part = x<<n; + unsigned right_part = x>>(31-n)>>1; + return left_part | right_part; +} + +/* + Return 1 when x can be represented as an n-bit, 2's-complement + number; 0 otherwise + Assume 1 <= n <= w + + Two's complement + TMAX = 2^(w-1) - 1 + TMIN = 2^(w-1) + + All bits are less than the nth bit. + Negative x should have their sign bit set. + + Check by truncating via shifting. + This takes care of the positive and negative cases with logical or arithmetic shift back. + + I also assumed w = 32 + */ +int fits_bits(int x, int n) { + return x == (x<<(32-n))>>(32-n); +} + +int main() { + printf("fits_bits: %x\n", fits_bits(7, 4)); + printf("fits_bits: %x\n", fits_bits(8, 4)); + return 0; + + printf("rotate_left: %x\n", rotate_left(0x12345678, 0)); + printf("rotate_left: %x\n", rotate_left(0x12345678, 4)); + printf("rotate_left: %x\n", rotate_left(0x12345678, 20)); + return 0; + + printf("lower_one_mask: %x\n", lower_one_mask(6)); + printf("lower_one_mask: %x\n", lower_one_mask(17)); + return 0; + + printf("int_size_is_32: %d\n", bad_int_size_is_32()); + return 0; + + printf("is little endian: %d\n", is_little_endian()); + printf("%d\n", 0xFF00); + printf("%x\n", leftmost_one(0xFF00)); + printf("%x\n", leftmost_one(0x6600)); + printf("%x\n", leftmost_one(0)); + + return 0; +} diff --git a/2/homework/2.73.c b/2/homework/2.73.c new file mode 100644 index 0000000..7ed0ca2 --- /dev/null +++ b/2/homework/2.73.c @@ -0,0 +1,113 @@ +#include <stdio.h> +#include <limits.h> +#include <assert.h> +#include <stdint.h> + +/* + Addition that saturates to TMIN or TMAX + 2^(w-2) + 2^(w-2) + w=4 + 0100 + 0100 + + + 1000 (-8) + Normally overflow wraps around to the other extreme. + z mod 2w + and do unsigned addition + + positive overflow -> TMAX + negative overflow -> TMIN + + for w=4 + 1000 + 1000 + + + 1000 + + 0100 + 0100 + + + 0111 + + z + + + note: you can apparently also do something like + + thing_is_true && (x = my_value) + + in c :/. + Now I did it with a weird method using masks based on booleans. +*/ +int saturating_add(int x, int y) { + int sum = x + y; + printf("sum: %x\n", sum); + int min = INT_MIN; + int did_negative_overflow = ((min & x) && (min & y) && !(min & sum)) - 1; + int did_positive_overflow = (!(min & x) && !(min & y) && (min & sum)) - 1; + sum |= INT_MIN & ~did_negative_overflow; + sum &= INT_MIN | did_negative_overflow; + sum |= INT_MAX & ~did_positive_overflow; + sum &= INT_MAX | did_positive_overflow; + return sum; +} + +/* + Determine whether arguments can be subtracted without overflow. + important to note is that the positive range of integers is shorter than the negative. + + positive [0, 2^{w-1} - 1] + negative [-2^{w-1}, 0] +*/ +int tsub_ok(int x, int y) { + if (y == INT_MIN) { + return 0; + } + int positive_overflow = x > 0 && y < 0 && x - y < 0; + int negative_overflow = x < 0 && y > 0 && x - y >= 0; + return !positive_overflow && !negative_overflow; +} + +/* + The result of 2.18 shows us + T2B(x*y) <=> U2B(x'*y') + but this is only for w bits. + In this case we are looking at the 2w bits. + + + */ +int signed_high_prod(int x, int y) { + int64_t result = (int64_t) x * y; + return result >> 32; +} +unsigned correct_unsigned_high_prod(unsigned x, unsigned y) { + uint64_t result = (uint64_t) x * y; + return result >> 32; +} +unsigned unsigned_high_prod(unsigned x, unsigned y) { + unsigned xl = x>>31; + unsigned yl = y>>31; + return signed_high_prod(x, y) + xl*y + yl*x; +} + +int main() { + /* assert(unsigned_high_prod(0xFFFFFFFF, 3) == correct_unsigned_high_prod(0xFFFFFFFF, 3)); */ + unsigned x = 0x12345678; + unsigned y = 0xFFFFFFFF; + + assert(correct_unsigned_high_prod(x, y) == unsigned_high_prod(x, y)); + return 0; + + printf("%d\n", tsub_ok(1, INT_MIN>>1)); + printf("%d\n", tsub_ok(1, (INT_MIN>>1) - 1)); + printf("%d\n", tsub_ok(1, INT_MIN)); + printf("%d\n", tsub_ok(INT_MIN, INT_MAX)); + printf("%d\n", -((INT_MIN>>1) - 1)); + printf("%d\n", INT_MAX); + return 0; + + printf("%x\n", INT_MIN); + printf("%x\n", saturating_add(INT_MIN, INT_MIN)); + printf("%x\n", saturating_add(4, 4)); + printf("%x\n", saturating_add(-3, 4)); + return 0; +} diff --git a/2/homework/2.77.c b/2/homework/2.77.c new file mode 100644 index 0000000..a2a5ed5 --- /dev/null +++ b/2/homework/2.77.c @@ -0,0 +1,108 @@ +#include <stdio.h> +#include <assert.h> +#include <limits.h> + +/* To do this we can use the formulas we derived earlier. + 17 = 16 + 1 + = x<<4 + x<<0 +*/ +int mul_by_17(int x) { + return (x<<4) + x; +} + +int mul_by_minus_7(int x) { + return - (x<<2) - (x<<1) - x; +} + +int mul_by_60(int x) { + return (x<<6) - (x<<2); +} + +int mul_by_minus_112(int x) { + return - (x<<7) + (x<<4); +} + +/* + Divide by power of 2. Assume 0 <= k < w - 1 + when x/k >= 0, rounding is already done towards 0. + + when x/k < 0, rounding is done to the next smallest integer. Instead we want to round to the next greatest integer. + We can add a bias to the negative x that ensures the division by k rounds downwards, but that the result is one k greater when division has a remainder. + + The example from the book uses the ternary conditional operator: + (x<0 ? x+(1<<k)-1 : x) >> k +*/ +int divide_power2(int x, int k) { + /* Get ones mask if msb is set */ + int msb = (x>>31); + int bias = (1<<k)-1; + /* Add bias if ones mask */ + x += msb & bias; + return x >> k; +} + +int mul3div4(int x) { + /* Multiply by 3 */ + x += (x<<1); + + int k = 2; + int msb = (x>>31); + int bias = (1<<k)-1; + /* Add bias if ones mask */ + x += msb & bias; + return x >> k; +} + +/* + I kind of missed the fact that the remainder is always less than four, so the only part of a number that causes rounding errors are those less than four. + So we could split up x into the bits that are four or greater, and bits that are less than four. + Rounding is then only relevant for the bits less than four. + + My method uses the remainder. No idea if it is a true generic solution, but it looks consistent with integer arithmetic rules. + */ +int threefourths(int x) { + int k = 2; + int msb = (x>>31); + int bias = (1<<k)-1; + /* Add bias if ones mask */ + int q = (x + (msb & bias)) >> k; + /* Calculate remainder so we know how to compensate when multiplying */ + int r = x - (q << k); + r = (((r<<1) + r) + ((r >> 31) & bias)) >> k; + return (q<<1) + q + r; +} + + +int main() { + /* 2.80 */ + assert(threefourths(8) == 6); + assert(threefourths(9) == 6); + assert(threefourths(10) == 7); + assert(threefourths(11) == 8); + assert(threefourths(12) == 9); + assert(threefourths(INT_MAX) == 1610612735); + + assert(threefourths(-8) == -6); + assert(threefourths(-9) == -6); + assert(threefourths(-10) == -7); + assert(threefourths(-11) == -8); + assert(threefourths(-12) == -9); + assert(threefourths(-INT_MAX) == -1610612735); + printf("%d\n", threefourths(-11)); + return 0; + + /* 2.79 */ + printf("%d\n", mul3div4(-15)); + return 0; + + /* 2.78 */ + printf("%d\n", divide_power2(-15, 1)); + return 0; + + /* 2.77 */ + printf("%d\n", mul_by_17(2)); + printf("%d\n", mul_by_minus_7(2)); + printf("%d\n", mul_by_60(2)); + printf("%d\n", mul_by_minus_112(1)); + return 0; +} diff --git a/2/homework/2.80.c b/2/homework/2.80.c new file mode 100644 index 0000000..4e6f3c5 --- /dev/null +++ b/2/homework/2.80.c @@ -0,0 +1,157 @@ +#include <stdio.h> +#include <stdlib.h> +#include <time.h> +#include <limits.h> + +unsigned bit_pattern_A(int k) { + return (~0)<<k; +} + +unsigned bit_pattern_B(int k, int j) { + return ~((~0)<<k) << j; +} + +float fraction_bit_pattern(unsigned Y, unsigned k) { + return 0; +} + +unsigned f2u(float f) { + union { + float f; + unsigned u; + } fu = { .f = f }; + return fu.u; +} + +/* + floating point number + The unsigned numbers can be compared. + The bits in the unsigned number can be mapped to bits in the floating point number in a monotonic way. + */ +int float_le(float x, float y) { + unsigned ux = f2u(x); + unsigned uy = f2u(y); + printf("ux: %x, uy: %x, ux<=uy: %d\n", ux, uy, ux<=uy); + + /* Get the sign bits */ + unsigned sx = ux >> 31; + unsigned sy = uy >> 31; + printf("sx: %d, sy: %d\n", sx, sy); + + /* Give an expression using only ux, uy, sx, and sy */ + printf("sx && !sy: %d, ((uy - sy) <= (ux - sx)): %d\n", sx && !sy, ux<=uy); + return (ux << 1 == 0 && uy << 1 == 0) + || (sx && !sy) + || (sx && sy) && (uy <= ux) + || ((!sx && !sy) && (ux <= uy)); +} + +int main() { + /* 2.85 + V=(2^E)*M + bias=2^(k-1) - 1 + k=8 + 0111 1111 + k bit exponent has values from (2^k)-bias + + (A) V=7.0 + E=(bias+2)-bias, has k-1 bit set plus 1, since (2^(k-1) -1)-bias == 0 + M=1/2+1/4=3/4, first two bits + 7.0=2^2(1+f)=4+4f=4+3 + (B) + largest integer --> largest odd integer + */ + return 0; + + /* 2.84 */ + printf("%d\n", f2u(0.1f)); + printf("%d\n", float_le(1, 0.1)); + return 0; + + /* 2.83 + Y=B2U(y), y is k bit word + I couldn't solve this one. Was stuck looking for patterns with arrows and tables instead of algebra. + + n = 0.yyyy.. + n<<k = y.yyyy.. + n<<k = Y + n + n<<k - n = Y + n(1<<k - 1) = Y + n = Y/(1<<k - 1) + + B. (a) 1/3 + (b) 6/15 -> 2/5 + (c) 19/63 + */ + return 0; + + /* + 32bit int and unsigned with arithmetic shift + */ + srand(time(NULL)); + int x = random(); + int y = random(); + unsigned ux = (unsigned) x; + unsigned uy = (unsigned) y; + printf("x: %d, y: %d\n", x, y); + /* + x<y == -x>-y + +x +y -> always true + -x -y -> alwyas true + -x +y -> x<y is true, -x>-y is also true, since the sign changes + +x -y -> x<y is false, -x>-y is also false, since the sign changes + */ + printf("A: %d\n", (x<y) == (-x>-y)); + /* + <=> + ((x<<4) + (y<<4) + y - x) mod 2^w + (16x + 16y + y - x) mod 2^w + */ + printf("B: %d\n", ((x+y)<<4) + y-x == 17*y+15*x); + /* + ~: + number --(~)--> -number -1 + + Using this observation we can do this (everything is under modulo 2^w, which is fine... right?): + ~x + ~y + 1: + -x - 1 - y - 1 + 1 + -x -y - 1 + -(x+y) - 1 + ~(x+y) + */ + printf("C: %d\n", ~x + ~y + 1 == ~(x+y)); + + /* + number --(unsigned)--> number + msb * 2^32 + + x + (msbx * 2^32) - (y + msby * 2^32) + x - y + msbx * 2^32 - msby * 2^32 + -(y-x) + msbx * 2^32 - msby * 2^32 + + -(unsigned)(y-x) + -((y-x) + (msbyx * 2^32)) + -(y-x) - (msbyx * 2^32) + + (msbx * 2^32 - msby * 2^32) = (msbyx * 2^32) = 0? + msbx = 0 and msby = 0 -> msbyx = 0 ? + 0100 - 0101 = 1111 -> if x > y and x,y>0 this expression is not true + */ + y = 4; + x = 5; + printf("D: %d\n", (ux-uy) == -(unsigned)(y-x)); + + /* + number -->>2--> floor(number/4) + number --<<4--> number*4 + + So the first two bits are always lost. And that means for negative and postive + two's complement number that the number either equals or is less than before. + */ + printf("E: %d\n", ((x >> 2) << 2) <= x); + return 0; + + /* 2.81 */ + printf("%x\n", bit_pattern_A(16)); + printf("%x\n", bit_pattern_B(8, 8)); + return 0; +} diff --git a/2/homework/2.87.c b/2/homework/2.87.c new file mode 100644 index 0000000..5d8a032 --- /dev/null +++ b/2/homework/2.87.c @@ -0,0 +1,6 @@ +#include <stdio.h> + +int main(void) { + printf("%f\n", 1023.0f/(1<<25)); + return 0; +} diff --git a/2/homework/2.88.c b/2/homework/2.88.c new file mode 100644 index 0000000..ba2cb5c --- /dev/null +++ b/2/homework/2.88.c @@ -0,0 +1,54 @@ +#include <stdio.h> +#include <limits.h> +#include <stdlib.h> + +/* + format A + s=1 + k=5, bias is 15 + n=3, fraction bits + + format B + s=1 + k=4 + n=4 + + convert A->B + round towards +inf + */ + +int C(double x, double y, double z) { + return (x + y) + z == x + (y + z); +} + +int D(double x, double y, double z) { + return (x * y) * z == x * (y * z); +} + +int main(void) { + /* 2.90 */ + + return 0; + + /* 2.89 + A. always true. double more precise so casting (float)(double) is the same as the original float. + B. not always true, if (x-y) results in a rounding error and not (dx-dy). + C. always true. no rounding error, the integer sums stay less than the smallest int that is not exactly representable as double. + D. not always true. You can reach odd values greater than the smallest odd value that can be represented exactly. The trick is to get different rounding on both sides of the ==. (very interesting result about double and float overflows, rounding to nearest even that is greater than 2^(n+1)+1) (2^30 + 1, 2^24 + 1, 2^23 + 1, any odd value greater than 2^53 + 1 will be rounded to an even number that is greater than 2^53 + 1. The amount of rounding depends on how much powers of two greater than 53 are needed to represent the number.) + E. not always true, 0 zero division is undefined. (No nan and inf since the original values are integers) + */ + int x = random(); + int y = random(); + int z = random(); + double dx = (double) x; + double dy = (double) y; + double dz = (double) z; + printf("x: %d, y: %d, z: %d\n", x, y, z); + printf("%d\n", (float) x == (float) dx); + printf("%d\n", C(1, 1<<31, 1<<31)); + printf("D: %d\n", D(INT_MAX, INT_MAX, INT_MAX)); + return 0; + + /* 2.88 in ora */ + return 0; +} diff --git a/2/homework/2.90.c b/2/homework/2.90.c new file mode 100644 index 0000000..8eefec3 --- /dev/null +++ b/2/homework/2.90.c @@ -0,0 +1,112 @@ +#include <assert.h> +#include <stdio.h> +#include <stdint.h> +#include <limits.h> +#include <math.h> +#include "../code/data/show-bytes.c" + + +float my_u2f(unsigned int my_u) { + assert(sizeof(unsigned int) == sizeof(float)); + union { + unsigned int u; + float f; + } my_union; + /* Apparently you cannot print the bytes of a float directly? like this printf("%x\n", f); */ + my_union.u = my_u; + return my_union.f; +} + +float fpwr2(int x) +{ + /* Result exponent and fraction */ + unsigned exp, frac; + unsigned u; + + int k = 8; + int n = 23; + + int bias = (1<<(k-1))-1; + int max_e = ((1<<k) - 2) - bias; + + if (x < 1-bias-n) { + /* Too small. Return 0.0 */ + exp = 0; + frac = 0; + } else if (x < 1-bias) { + /* Denormalized, [(1-bias-n), (1-bias)] [-139, -126] */ + exp = 0; + frac = 1<<(x+1-bias-n); + } else if (x<=max_e) { + /* Normalized */ + exp = x+bias; + frac = 0; + } else { + /* Too big. Return +oo */ + exp = (1<<8)-1; + frac = 0; + } + + /* Pack exp and frac into 32 bits */ + u = (exp << 23) | frac; + /* Return as float */ + return my_u2f(u); +} + + +int main(void) { + + /* 2.90 */ + printf("%f\n", fpwr2(-1)); /* 65536 */ + printf("%f\n", fpwr2(16)); /* 65536 */ + printf("%f\n", fpwr2(15)); /* 32768 */ + printf("%f\n", fpwr2(14)); /* 16384 */ + printf("%f\n", fpwr2(13)); /* 8192 */ + printf("%f\n", fpwr2(12)); /* 4096 */ + printf("%f\n", fpwr2(11)); /* 2048 */ + printf("%f\n", fpwr2(10)); /* 1024 */ + printf("%f\n", fpwr2(128)); + return 0; + + /* 2.91 */ + printf("%x\n", 0b01000000010010010000111111011011); + /* + 0 10000000 10010010000111111011011 + E = 128-127 = 1 + M = 1 + f + f = (2^22+2^19+2^16+2^11+2^10+2^9+2^8+2^7+2^6+2^4+2^3+2^1+2^0)/2^23 + V = (2^E)(M) + + 13176795/4194304 + + 22/7 = 2(1+f) + 11/7 = (1+f) + 4/7 = f + + n = 0.yyy = f + n = Y/((1<<k) - 1) + n = 4/((1<<3) - 1) + 0 10000000 [100]+ + */ + show_float(22.0f/7.0f); + printf("%b\n", 0x40492492); + /* so we have 22/7 + 0 10000000 10010010010010010010010 + and the approx + 0 10000000 10010010000111111011011 + at the 9th position the values diverge + */ + return 0; + + /* 2.90 */ + printf("%f\n", fpwr2(-1)); /* 65536 */ + printf("%f\n", fpwr2(16)); /* 65536 */ + printf("%f\n", fpwr2(15)); /* 32768 */ + printf("%f\n", fpwr2(14)); /* 16384 */ + printf("%f\n", fpwr2(13)); /* 8192 */ + printf("%f\n", fpwr2(12)); /* 4096 */ + printf("%f\n", fpwr2(11)); /* 2048 */ + printf("%f\n", fpwr2(10)); /* 1024 */ + printf("%f\n", fpwr2(128)); + return 0; +} diff --git a/2/homework/2.92.c b/2/homework/2.92.c new file mode 100644 index 0000000..bf1096e --- /dev/null +++ b/2/homework/2.92.c @@ -0,0 +1,402 @@ +#include <assert.h> +#include <stdio.h> +#include <stdint.h> +#include <limits.h> +#include <math.h> +#include "../code/data/show-bytes.c" + +typedef unsigned float_bits; + +#define M ~0 + +unsigned i2u(int i) { + union { + unsigned u; + int i; + } ui; + ui.i = i; + return ui.u; +} + +float u2f(unsigned int my_u) { + assert(sizeof(unsigned int) == sizeof(float)); + union { + unsigned int u; + float f; + } my_union; + /* Apparently you cannot print the bytes of a float directly? like this printf("%x\n", f); */ + my_union.u = my_u; + return my_union.f; +} + +float fpwr2(int x) +{ + /* Result exponent and fraction */ + unsigned exp, frac; + unsigned u; + + int k = 8; + int n = 23; + + int bias = (1<<(k-1))-1; + int max_e = ((1<<k) - 2) - bias; + + if (x < 1-bias-n) { + /* Too small. Return 0.0 */ + exp = 0; + frac = 0; + } else if (x < 1-bias) { + /* Denormalized, [(1-bias-n), (1-bias)] [-139, -126] */ + exp = 0; + frac = 1<<(x+1-bias-n); + } else if (x<=max_e) { + /* Normalized */ + exp = x+bias; + frac = 0; + } else { + /* Too big. Return +oo */ + exp = (1<<8)-1; + frac = 0; + } + + /* Pack exp and frac into 32 bits */ + u = (exp << 23) | frac; + /* Return as float */ + return u2f(u); +} + +/* + int and unsigned and their operations are allowed. + */ +float_bits float_denorm_zero(float_bits f) { + unsigned sign = f>>31; + unsigned exp = f>>23 & 0xFF; + unsigned frac = f & 0x7FFFFF; + if (exp == 0) { + frac = 0; + } + return (sign << 31) | (exp << 23) | frac; +} + +float_bits float_negate(float_bits f) { + unsigned is_valid_exp = (f>>23) ^ 0xFF; + unsigned frac = f & 0x7FFFFF; + if (!is_valid_exp && frac) return f; + return (1<<31) ^ f; +} + +float_bits float_absval(float_bits f) { + unsigned is_valid_exp = (f>>23) ^ 0xFF; + unsigned frac = f & 0x7FFFFF; + if (!is_valid_exp && frac) return f; + return ~(1<<31) & f; +} + +float_bits float_twice(float_bits f) { + /* + */ + unsigned sign = f>>31; + unsigned exp = (f>>23) & 0xFF; + unsigned frac = f & 0x7FFFFF; + unsigned is_valid_exp = exp ^ 0xFF; + if (!is_valid_exp) return f; + + if (!exp) { + /* + Denormalized because we have a zero exponent + f<<1 + */ + return (sign<<31) | (frac<<1); + } else { + /* + Normalized value. + = (2^k(1+f))*2 + = 2^(k+1)(1+f) + */ + unsigned twice_exp = exp + 1; + if (twice_exp == 0xFF) { + frac = 0; + } + return (sign<<31) | (twice_exp<<23) | frac; + } +} + +float_bits float_half(float_bits f) { + unsigned sign = f>>31; + unsigned exp = (f>>23) & 0xFF; + unsigned frac = f & 0x7FFFFF; + unsigned is_valid_exp = exp ^ 0xFF; + if (!is_valid_exp) return f; + + if (!exp) { + /* + Denormalized because we have a zero exponent + f>>1 + */ + if (frac&1 && frac^1) { + /* + Round to nearest even? + */ + frac >>= 1; + frac += frac&1; + } else { + frac >>= 1; + } + return (sign<<31) | frac; + } else { + /* + Normalized value. + */ + unsigned half_exp = exp; + /* Can we halve with exp? */ + if ((half_exp - 1) == 0) { + /* Is it the value in the middle between norm and denorm? */ + if ((frac ^ 0x7FFFFF) == 0) { + frac = 0; + } else { + /* Otherwise, normally divide the (1+f) by two */ + half_exp -= 1; + if (frac&1 && frac^1) { + frac >>= 1; + frac += frac&1; + } else { + frac >>= 1; + } + frac |= 1<<22; + } + } else { + half_exp -= 1; + } + return (sign<<31) | (half_exp<<23) | frac; + } +} + +/* + Compute (int) f. + If conversion causes overflow or f is NaN, return 0x80 00 00 00 + */ +int float_f2i(float_bits f) { + int invalid = 0x80000000; + unsigned sign = f>>31; + unsigned exp = (f>>23) & 0xFF; + unsigned frac = f & 0x7FFFFF; + unsigned is_valid_exp = exp ^ 0xFF; + if (!is_valid_exp) return invalid; + + unsigned bias = (1<<7) - 1; + if (exp < bias) return 0; + exp -= bias; + /* + Smallest odd that cannot be represented exactly + 2^(n+1) + 1 + */ + if (exp < 24) { + int result = (1<<exp) + (frac>>(23 - exp)); + if (sign) { + result = ~result + 1; + } + return result; + } + if (exp < 31) { + int result = (1<<exp) + (frac<<(exp - 23)); + if (sign) { + result = ~result + 1; + } + return result; + } + return invalid; +} + +float_bits float_i2f(int i) { + if (i==0) return 0; + /* + Need to calculate exp and frac based on integer, so we will take apart the integer into exp and frac using the fundamenal property of division. + p = q + r, where q and r are integers and q is the result of integer division of p + */ + unsigned sign = i>>31; + int exp, frac, k, n, bias; + + k = 8; + n = 23; + bias = (1<<(k-1))-1; + exp = bias; + frac = 0; + + if (i==INT_MIN) { + /* Special case since ~i+1=i, if i=INT_MIN */ + return (sign<<31) | ((exp+31)<<23) | 0; + } + + /* Get the greatest power of 2, p2 and remainder */ + int p2, rem; + int u = (i & ~sign) | ((~i + 1) & sign); + int u_orig = u; + int b16, b8, b4, b2, b1, b0; + + b16 = (!!(u>>16))<<4; + u >>= b16; + b8 = (!!(u>>8))<<3; + u >>= b8; + b4 = (!!(u>>4))<<2; + u >>= b4; + b2 = (!!(u>>2))<<1; + u >>= b2; + b1 = (!!(u>>1)); + + p2 = b16 + b8 + b4 + b2 + b1; + exp += p2; + rem = u_orig - (1<<p2); + + /* How much greater than precision are we */ + int prec = (p2-23); + int prec2 = (1<<prec); + + if (rem == 0) { + frac = 0; + } else { + if (p2 > 23) { + /* Outside of float32 precision */ + + /* Special case, Is remainder greater than half precision removed from highest power? */ + if ((1<<p2) - (prec2>>1) <= rem) { + /* Round up into next power level */ + frac = 0; + exp += 1; + } else { + /* Encode remainder as fraction with prec denom */ + frac = rem>>prec; + if (prec>1) { + /* Rounding is non binary, need to check if round to even applies or round up */ + int r = rem%prec2; + if (r > (prec2>>1)) { + frac += 1; + } else if (r==(prec2>>1)) { + frac += frac&1; + } + } else { + /* Binary rounding is easy, even rem don't need it and odd rem need it if the result is odd */ + frac += rem&1 && frac&1; + } + } + } else { + /* Within precision, just encode remainder as fraction with prec denom */ + frac = (rem<<(23-p2)); + } + } + return (sign<<31) | (exp<<23) | frac; + /* + 1 1001 1101 [0]+ + 1 1001 1100 [1]+ + */ + /* + Denormalized + V = M * 2^E + M = f < 1-e + E = 1 - bias + <=> V < 1 + + Normalized + M = 1 + f + V = 1 = 2^E *(1+f) <==> e>=bias, e=bias <=> V=(2^0)(1+f) + E = e-bias + bias=127 + + smallest int + -(2^31) + biggest int + (2^31)-1 + 1 <> 0 0111 1111 [0]+ + 2 <> 0 1000 0000 [0]+ + 3 <> 0 1000 0000 1[0]+ + 4 <> 0 1000 0001 [0]+ + 5 <> 0 1000 0001 01[0]+ + 6 <> 0 1000 0001 1[0]+ + 7 <> 0 1000 0001 11[0]+ + 8 <> 0 1000 0010 000[0]+ + 9 <> 0 1000 0010 001[0]+ + 10 <> 0 1000 0010 010[0]+ + 11 <> 0 1000 0010 011[0]+ + */ + return 1; +} + +int main(void) { + /* 2.97 */ + int j; + for (j=INT_MIN; j<INT_MAX; j++) { + float v = u2f(float_i2f(j)); + int result = (((float) j) == v); + /* show_float((float) j); */ + /* show_float(v); */ + if (!result) { + printf("want: %f, got: %f\n", ((float) j), v); + show_float((float) j); + show_float(v); + } + assert(result); + } + return 0; + + /* 2.96 */ + unsigned i; + for (i=0; i<M; i++) { + int v = float_f2i(i); + int result = isnan(u2f(i)) || (((int) u2f(i)) == v); + if (!result) { + printf("want: %d, got: %d\n", ((int) u2f(i)), v); + show_float(u2f(i)); + } + assert(result); + } + return 0; + + /* 2.95 */ + for (i=0; i<M; i++) { + float v = u2f(float_half(i)); + int result = isnan(u2f(i)) || (0.5f*u2f(i) == v); + if (!result) { + printf("want: %f, got: %f\n", 0.5f*u2f(i), v); + show_float(u2f(1)); + show_float(u2f(i)); + show_float(0.5f*u2f(i)); + show_float(v); + } + assert(result); + } + return 0; + + /* 2.94 */ + for (i=0; i<M; i++) { + float v = u2f(float_twice(i)); + int result = isnan(u2f(i)) || (2*u2f(i) == v); + if (!result) { + printf("want: %f, got: %f\n", 2*u2f(i), v); + show_float(2*u2f(i)); + show_float(v); + } + assert(result); + } + return 0; + + /* 2.93 */ + for (i=0; i<M; i++) { + float v = u2f(float_absval(i)); + int result = isnan(v) || (fabsf(u2f(i)) == v); + if (!result) { + printf("%f\n", fabsf(u2f(i))); + } + assert(result); + } + return 0; + + /* 2.92 */ + for (i=0; i<M; i++) { + float v = u2f(float_negate(i)); + int result = isnan(v) || (-u2f(i) == v); + if (!result) { + printf("%f\n", u2f(i)); + } + assert(result); + } + return 0; +} diff --git a/2/homework/2.96.c b/2/homework/2.96.c new file mode 100644 index 0000000..e9ca8d9 --- /dev/null +++ b/2/homework/2.96.c @@ -0,0 +1,8 @@ +#import "stdio.h" + + + +int main(void) { + + return 0; +} diff --git a/2/homework/285.ora b/2/homework/285.ora Binary files differnew file mode 100644 index 0000000..7f9cc9d --- /dev/null +++ b/2/homework/285.ora diff --git a/2/homework/bytes_structure_2.71.c b/2/homework/bytes_structure_2.71.c new file mode 100644 index 0000000..61ead1c --- /dev/null +++ b/2/homework/bytes_structure_2.71.c @@ -0,0 +1,67 @@ +#include <stdio.h> +#include <string.h> + +typedef unsigned packed_t; + +/* + 3 2 1 0 + byte byte byte byte + 1000 1100 1110 1111 + xbyte(..., 2); + >> 8 + 0000 0000 1000 1100 + & 0xFF + 0000 0000 0000 1100 + + 0 <= x < 7 -> id + -8 < x < 0 -> minus +*/ +int xbyte(packed_t word, int bytenume); +int xbyte(packed_t word, int bytenum) { + int max_bytes = 3; + int max_bits = max_bytes << 3; + int shift_bits = (3 - bytenum) << 3; + return (int) word << shift_bits >> max_bits; +} + +/* + Copy integer into buffer if space is available + WARNING: The following code is buggy + + size_t is an unsigned. So one of the operands gets casted. + Either + int -> unsigned + or + unsigned -> int + + apparently the result of unsigned - int or int - unsigned -> unsigned + */ +void buggy_copy_int(int val, void *buf, int maxbytes) { + /* + Check if maxbytes will cause problems when converted to unsigned. + */ + if (maxbytes < 0) { + return; + } + if (maxbytes >= sizeof(val)) { + memcpy(buf, (void *) &val, sizeof(val)); + } +} + +int main() { + int maxbytes = 4; + char buf[maxbytes]; + int i; + for (i=0; i<maxbytes; ++i) { + buf[i] = 'a'; + } + + buggy_copy_int(32, buf, maxbytes); + for (i=0; i<maxbytes; ++i) { + printf("%x\n", buf[i]); + } + return 0; + + printf("%x\n", xbyte(0x0000FF00, 1)); + return 0; +} diff --git a/2/homework/implement_calloc.c b/2/homework/implement_calloc.c new file mode 100644 index 0000000..62c3804 --- /dev/null +++ b/2/homework/implement_calloc.c @@ -0,0 +1,28 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +void *my_calloc(size_t nmemb, size_t size) { + if (nmemb == 0 || size == 0) { + return NULL; + } + /* Check if invariant of multiplication is broken by overflow */ + size_t membytes = nmemb * size; + if (membytes/nmemb != size) { + return NULL; + } + void *mem_or_null = malloc(membytes); + if (mem_or_null == NULL) { + return NULL; + } + + return memset(mem_or_null, 0, membytes); +} + +int main() { + char *buf = my_calloc(10, 15); + int i; + for (i=0; i<10*15; ++i) + printf("%c", 97 + buf[i]); + return 0; +} diff --git a/2/homework/logical_and_or.c b/2/homework/logical_and_or.c new file mode 100644 index 0000000..811fb09 --- /dev/null +++ b/2/homework/logical_and_or.c @@ -0,0 +1,8 @@ +#include <stdio.h> + +int main() { + if (0 && 1) { + printf("hi"); + } + printf("%d\n", (0 && 1) || 0); +} diff --git a/2/homework/shift_by_w_minus_k.c b/2/homework/shift_by_w_minus_k.c new file mode 100644 index 0000000..de595c9 --- /dev/null +++ b/2/homework/shift_by_w_minus_k.c @@ -0,0 +1,37 @@ +#include <stdio.h> +#include <limits.h> + +typedef unsigned char *byte_pointer; + +void show_bytes(byte_pointer start, size_t len) { + int i; + for (i = 0; i < len; i++) { + printf(" %.2x", start[i]); + } + printf("\n"); +} + +void show_int(int x) { + show_bytes((byte_pointer) &x, sizeof(int)); +} + +void show_float(float x) { + show_bytes((byte_pointer) &x, sizeof(float)); +} + +void show_pointer(void *x) { + show_bytes((byte_pointer) &x, sizeof(void *)); +} + +int main() { + int A = -1; + int w = sizeof(int)<<3; + int k = 0; + int shifted_off_by_one = (A<<(w-k - 1)); + int shifted = shifted_off_by_one + shifted_off_by_one; + printf("w: %d, k: %d, A<<(w-k): %d\n", w, k, shifted); + show_int(shifted); + + printf("%d\n", ((1<<(w - 1)) & INT_MAX) && 1); + +} diff --git a/3/3_data_formats/main.c b/3/3_data_formats/main.c new file mode 100644 index 0000000..7fac153 --- /dev/null +++ b/3/3_data_formats/main.c @@ -0,0 +1,16 @@ +#include <stdio.h> + +void multstore(long, long, long *); + +long mult2(long a, long b) { + long s = a * b; + return s; +} + +int main() { + long d; + multstore(2, 3, &d); + printf("2 * 3 --> %ld\n", d); + return 0; +} + diff --git a/3/3_data_formats/mstore/mstore.c b/3/3_data_formats/mstore/mstore.c new file mode 100644 index 0000000..cdcf205 --- /dev/null +++ b/3/3_data_formats/mstore/mstore.c @@ -0,0 +1,6 @@ +long mult2(long, long); + +void multstore(long x, long y, long *dest) { + long t = mult2(x, y); + *dest = t; +} diff --git a/3/3_data_formats/mstore/mstore.s b/3/3_data_formats/mstore/mstore.s new file mode 100644 index 0000000..e215a2b --- /dev/null +++ b/3/3_data_formats/mstore/mstore.s @@ -0,0 +1,21 @@ + .file "mstore.c" + .text + .globl multstore + .type multstore, @function +multstore: +.LFB0: + .cfi_startproc + pushq %rbx + .cfi_def_cfa_offset 16 + .cfi_offset 3, -16 + movq %rdx, %rbx + call mult2@PLT + movq %rax, (%rbx) + popq %rbx + .cfi_def_cfa_offset 8 + ret + .cfi_endproc +.LFE0: + .size multstore, .-multstore + .ident "GCC: (GNU) 12.3.0" + .section .note.GNU-stack,"",@progbits diff --git a/3/4_register_and_addresses/main.c b/3/4_register_and_addresses/main.c new file mode 100644 index 0000000..f767ee6 --- /dev/null +++ b/3/4_register_and_addresses/main.c @@ -0,0 +1,27 @@ +#include <stdio.h> + +void decode1(long *xp, long *yp, long *zp) { + long x = *xp; + long y = *yp; + long z = *zp; + + *yp = x; + *zp = y; + *xp = z; +} + +long scale(long x, long y, long z) { + long t = x + 4 * y + 12 * z; + return t; +} + +long scale3(long x, long y, long z) { + long t = 10 * y + z + x * y; + return t; +} + +int main(void) { + char c = 0xC0; + int x = (int) c; + printf("%d", x); +} diff --git a/3/5_arith_and_logic/movq_size.s b/3/5_arith_and_logic/movq_size.s new file mode 100644 index 0000000..3d525df --- /dev/null +++ b/3/5_arith_and_logic/movq_size.s @@ -0,0 +1,16 @@ + .file "xorq_size.c" + .text + .section .text.startup,"ax",@progbits + .p2align 4 + .globl main + .type main, @function +main: +.LFB0: + .cfi_startproc + movl $0, %eax + ret + .cfi_endproc +.LFE0: + .size main, .-main + .ident "GCC: (GNU) 12.3.0" + .section .note.GNU-stack,"",@progbits diff --git a/3/5_arith_and_logic/remdiv.c b/3/5_arith_and_logic/remdiv.c new file mode 100644 index 0000000..8d3c957 --- /dev/null +++ b/3/5_arith_and_logic/remdiv.c @@ -0,0 +1,12 @@ +#include <stdio.h> + +void remdiv(long x, long y, long *qp, long *rp) { + long q = x/y; + long r = x%y; + *qp = q; + *rp = r; +} + +int main() { + remdiv(0,0,0,0); +} diff --git a/3/5_arith_and_logic/remdiv.s b/3/5_arith_and_logic/remdiv.s new file mode 100644 index 0000000..61c66df --- /dev/null +++ b/3/5_arith_and_logic/remdiv.s @@ -0,0 +1,38 @@ + .file "remdiv.c" + .text + .globl remdiv + .type remdiv, @function +remdiv: +.LFB23: + .cfi_startproc + movq %rdi, %rax + movq %rdx, %r8 + xorq %rdx, %rdx + divq %rsi + movq %rax, (%r8) + movq %rdx, (%rcx) + ret + .cfi_endproc +.LFE23: + .size remdiv, .-remdiv + .globl main + .type main, @function +main: +.LFB24: + .cfi_startproc + subq $8, %rsp + .cfi_def_cfa_offset 16 + movl $0, %ecx + movl $0, %edx + movl $0, %esi + movl $0, %edi + call remdiv@PLT + movl $0, %eax + addq $8, %rsp + .cfi_def_cfa_offset 8 + ret + .cfi_endproc +.LFE24: + .size main, .-main + .ident "GCC: (GNU) 12.3.0" + .section .note.GNU-stack,"",@progbits diff --git a/3/5_arith_and_logic/reverse_assemble.c b/3/5_arith_and_logic/reverse_assemble.c new file mode 100644 index 0000000..6413f98 --- /dev/null +++ b/3/5_arith_and_logic/reverse_assemble.c @@ -0,0 +1,23 @@ +#include <stdio.h> + +/* + * x in %rdi, y in %rsi, z in %rdx + * arith3: + * orq %rsi, %rdx + * sarq $9, %rdx + * notq %rdx + * movq %rdx, %bax <------- what is this register?? + * subq %rsi, %rbx + * ret + */ +short arith3(short x, short y, short z) { + short p1 = z | y; + short p2 = p1>>9; + short p3 = ~p2; + short p4 = p3; + return p4; +} + +int main() { + +} diff --git a/3/5_arith_and_logic/sarl.c b/3/5_arith_and_logic/sarl.c new file mode 100644 index 0000000..51e6305 --- /dev/null +++ b/3/5_arith_and_logic/sarl.c @@ -0,0 +1,11 @@ +#include <stdio.h> + +long shift_left4_rightn(long x, long n) { + x <<= 4; + x >>= n; + return x; +} + +int main() { + printf("%d", shift_left4_rightn(15, 5)); +} diff --git a/3/5_arith_and_logic/store_uprod.c b/3/5_arith_and_logic/store_uprod.c new file mode 100644 index 0000000..0009e09 --- /dev/null +++ b/3/5_arith_and_logic/store_uprod.c @@ -0,0 +1,11 @@ +#include <inttypes.h> + +typedef unsigned __int128 uint128_t; + +void store_uprod(uint128_t *dest, uint64_t x, uint64_t y) { + *dest = x * (uint128_t) y; +} + +int main() { + return 0; +} diff --git a/3/5_arith_and_logic/store_uprod.s b/3/5_arith_and_logic/store_uprod.s new file mode 100644 index 0000000..a099e77 --- /dev/null +++ b/3/5_arith_and_logic/store_uprod.s @@ -0,0 +1,27 @@ + .file "store_uprod.c" + .text + .globl store_uprod + .type store_uprod, @function +store_uprod: +.LFB0: + .cfi_startproc + movq %rsi, %rax + mulq %rdx + movq %rax, (%rdi) + movq %rdx, 8(%rdi) + ret + .cfi_endproc +.LFE0: + .size store_uprod, .-store_uprod + .globl main + .type main, @function +main: +.LFB1: + .cfi_startproc + movl $0, %eax + ret + .cfi_endproc +.LFE1: + .size main, .-main + .ident "GCC: (GNU) 12.3.0" + .section .note.GNU-stack,"",@progbits diff --git a/3/5_arith_and_logic/xorq_size.c b/3/5_arith_and_logic/xorq_size.c new file mode 100644 index 0000000..5751590 --- /dev/null +++ b/3/5_arith_and_logic/xorq_size.c @@ -0,0 +1,5 @@ +int main() { + int x = 5; + x ^= x; + return 0; +} diff --git a/3/5_arith_and_logic/xorq_size.s b/3/5_arith_and_logic/xorq_size.s new file mode 100644 index 0000000..ed88d9a --- /dev/null +++ b/3/5_arith_and_logic/xorq_size.s @@ -0,0 +1,16 @@ + .file "xorq_size.c" + .text + .section .text.startup,"ax",@progbits + .p2align 4 + .globl main + .type main, @function +main: +.LFB0: + .cfi_startproc + xorl %eax, %eax + ret + .cfi_endproc +.LFE0: + .size main, .-main + .ident "GCC: (GNU) 12.3.0" + .section .note.GNU-stack,"",@progbits diff --git a/3/6_control/20_op_bias.c b/3/6_control/20_op_bias.c new file mode 100644 index 0000000..b071eb9 --- /dev/null +++ b/3/6_control/20_op_bias.c @@ -0,0 +1,10 @@ +#define OP < + +// x <- %rdi +// %rbx <- 15 + (x), bias to round towards zero +// ZF, SF <- %rdi & %rdi, check if pos or neg +// %rbx <- x if x >= 0, set to unbiased if pos +// %rbx <- %rbx >> 4, divide by 16 +short arith(short x) { + return x / 16; +} diff --git a/3/6_control/21_test_cmov.c b/3/6_control/21_test_cmov.c new file mode 100644 index 0000000..a90d178 --- /dev/null +++ b/3/6_control/21_test_cmov.c @@ -0,0 +1,20 @@ +#include <stdio.h> + +// Remember that jumps flip conditionals +// Also testq rdi rdi and jge test if the sign bit is set +short test(short x, short y) { + short val = 12 + y; + if (x < 0) { + if (x >= y) + val = x | y; + else + val = x * y; + } else if (y >= 10) { + val = x / y; + } + return val; +} + +int main(void) { + return 0; +} diff --git a/3/6_control/22_loop.c b/3/6_control/22_loop.c new file mode 100644 index 0000000..73c7710 --- /dev/null +++ b/3/6_control/22_loop.c @@ -0,0 +1,51 @@ +#include <limits.h> +#include <stdint.h> +#include <stdio.h> +// do +// body +// while (test); +// +// loop: +// body +// t = test; +// if (t) +// goto loop; + +typedef int64_t fact_t; + +long fact_do(long n) +{ + long result = 1; + do { + result *= n; + n = n-1; + } while (n > 1); + return result; +} + +int tmult_ok(fact_t x, fact_t y) +{ + fact_t p = x*y; + return !x || p/x == y; +} + +fact_t fact_do_int(size_t n) +{ + fact_t result = 1; + do { + if (tmult_ok(result, n)) { + result *= n; + n = n-1; + } else { + printf("would overflow this iter, n=%ld\n", n); + n = 0; + } + } while (n > 1); + return result; +} + +int main(void) { + size_t f = 20; + printf("result: %ld, max: %ld, less: %d", fact_do_int(f), INT64_MAX, fact_do_int(f) < INT64_MAX); + return 0; +} diff --git a/3/6_control/23_reverse_engineer_loop.c b/3/6_control/23_reverse_engineer_loop.c new file mode 100644 index 0000000..922b317 --- /dev/null +++ b/3/6_control/23_reverse_engineer_loop.c @@ -0,0 +1,28 @@ +short dw_loop(short x) +{ + short y = x/9; + short *p = &x; + short n = 4*x; + do { + x += y; + (*p) += 5; + n += 2; + } while (n > 0); + return x; +} + +// x in %rdi +// dw_loop: +// movq %rdi, %rdx # %rbx <- x +// movq %rdi, %rcx # %rcx <- x +// idivq $9, %rcx # %rcx (y) <- x / 9 +// leaq (,%rdi,4), %rdx # %rdx (n) <- x * 4 +// .L2: +// leaq 5(%rbx,%rcx), %rcx # %rbx (x) <- 5 + %rbx (x) + %rcx (y) +// subq $1, %rdx # %rdx (n) <- n - 1 +// testq %rdx, %rdx # n > 0 ? +// jg .L2 # if n > 0, goto .L2 +// rep; ret +// +// A. x in rbx, y in rcx, n in rdx +// B. The pointer is never used besides incrementing the value at the address. So it is replaced by a incrementing instruction in the loop. diff --git a/3/6_control/24_while_loop.c b/3/6_control/24_while_loop.c new file mode 100644 index 0000000..a3367fc --- /dev/null +++ b/3/6_control/24_while_loop.c @@ -0,0 +1,24 @@ +// while (test) +// body +// +// goto test; +// loop: +// body; +// test: +// t = test; +// if (t) +// goto loop; + +short loop_while(short a, short b) +{ + short result = ; + while () { + result = ; + a = ; + } + return result; +} + +int main(void) { + return 0; +} diff --git a/3/6_control/absdiff_goto.c b/3/6_control/absdiff_goto.c new file mode 100644 index 0000000..dfcb3be --- /dev/null +++ b/3/6_control/absdiff_goto.c @@ -0,0 +1,39 @@ +#include <stdio.h> + +// if (!t) +// goto false; +// then- +// goto done; +// false: +// else- +// goto done; +// done: +// ... +long gotodiff_se(long x, long y) +{ + long result; + if (x >= y) + goto x_ge_y; + lt_cnt++; + result = y - x; + return result; + +x_get_y: + ge_cnt++; + result = x - y; + return result; +} + +long gotodiff_se_alternate(long x, long y) +{ + long result; + if (x < y) + goto x_le_y; + ge_cnt++; + result = x - y; + return result; +x_le_y: + lt_cnt++; + result = y - x; + return result; +} diff --git a/3/6_control/comp.c b/3/6_control/comp.c new file mode 100644 index 0000000..beba875 --- /dev/null +++ b/3/6_control/comp.c @@ -0,0 +1,36 @@ +#include <stdio.h> + +typedef char data_t; + +#define COMP <= + +// a in rdx, b in rsi +// +// cmpl %esi, %edi (Compare long (double word, or 4 bytes). (a - b) ) +// setl %al (set lower? %rax return value) +// +// COMP is <, and data_t is 32 bits so maybe int or unsigned int or float +// +// cmpw %si, %di (Compare word (a-b), short) +// setge %al (Greater than or equal >=) +// +// cmpb %sil, %dil (Compare byte (a-b)) +// setbe %al (Comp <=) +// +// cmpq %rsi, %rdi (Compare 8 bytes quad words (long , double, char *)) +// setne %al +int comp(data_t a, data_t b) { + return a COMP b; +} + +#define TEST > + +int test(data_t a) { + return a TEST 0; +} + +int main() { + printf("%x hello world", comp(1, 2)); + return 0; +} + diff --git a/3/6_control/cond.c b/3/6_control/cond.c new file mode 100644 index 0000000..8b647bf --- /dev/null +++ b/3/6_control/cond.c @@ -0,0 +1,6 @@ +void cond(short a, short *p) +{ + if (a && *p < a) { + *p = a; + } +} diff --git a/3/6_control/missing.c b/3/6_control/missing.c new file mode 100644 index 0000000..1b8067b --- /dev/null +++ b/3/6_control/missing.c @@ -0,0 +1,13 @@ +short test(short x, short y, short z) { + short val = (z+y) - x; + if (z > 5) { + if (y > 2) { + val = x/z; + } else { + val = x/y; + } + } else if (z < 3) { + val = z/y; + } + return val; +} diff --git a/code/intro/hello.c b/code/intro/hello.c deleted file mode 100644 index b9dbb17..0000000 --- a/code/intro/hello.c +++ /dev/null @@ -1,7 +0,0 @@ -#include <stdio.h> - -int main() -{ - printf("hello, world\n"); - return 0; -} diff --git a/flake.lock b/flake.lock new file mode 100644 index 0000000..7479268 --- /dev/null +++ b/flake.lock @@ -0,0 +1,173 @@ +{ + "nodes": { + "flake-utils": { + "inputs": { + "systems": "systems" + }, + "locked": { + "lastModified": 1694529238, + "narHash": "sha256-zsNZZGTGnMOf9YpHKJqMSsa0dXbfmxeoJ7xHlrt+xmY=", + "owner": "numtide", + "repo": "flake-utils", + "rev": "ff7b65b44d01cf9ba6a71320833626af21126384", + "type": "github" + }, + "original": { + "owner": "numtide", + "repo": "flake-utils", + "type": "github" + } + }, + "flake-utils_2": { + "inputs": { + "systems": "systems_2" + }, + "locked": { + "lastModified": 1689068808, + "narHash": "sha256-6ixXo3wt24N/melDWjq70UuHQLxGV8jZvooRanIHXw0=", + "owner": "numtide", + "repo": "flake-utils", + "rev": "919d646de7be200f3bf08cb76ae1f09402b6f9b4", + "type": "github" + }, + "original": { + "owner": "numtide", + "repo": "flake-utils", + "type": "github" + } + }, + "nix-filter": { + "locked": { + "lastModified": 1694857738, + "narHash": "sha256-bxxNyLHjhu0N8T3REINXQ2ZkJco0ABFPn6PIe2QUfqo=", + "owner": "numtide", + "repo": "nix-filter", + "rev": "41fd48e00c22b4ced525af521ead8792402de0ea", + "type": "github" + }, + "original": { + "owner": "numtide", + "repo": "nix-filter", + "type": "github" + } + }, + "nix-github-actions": { + "inputs": { + "nixpkgs": [ + "poetry2nix", + "nixpkgs" + ] + }, + "locked": { + "lastModified": 1688870561, + "narHash": "sha256-4UYkifnPEw1nAzqqPOTL2MvWtm3sNGw1UTYTalkTcGY=", + "owner": "nix-community", + "repo": "nix-github-actions", + "rev": "165b1650b753316aa7f1787f3005a8d2da0f5301", + "type": "github" + }, + "original": { + "owner": "nix-community", + "repo": "nix-github-actions", + "type": "github" + } + }, + "nixpkgs": { + "locked": { + "lastModified": 1697009197, + "narHash": "sha256-viVRhBTFT8fPJTb1N3brQIpFZnttmwo3JVKNuWRVc3s=", + "owner": "NixOS", + "repo": "nixpkgs", + "rev": "01441e14af5e29c9d27ace398e6dd0b293e25a54", + "type": "github" + }, + "original": { + "id": "nixpkgs", + "type": "indirect" + } + }, + "nixpkgs-terraform-providers-bin": { + "inputs": { + "nixpkgs": [ + "nixpkgs" + ] + }, + "locked": { + "lastModified": 1697070923, + "narHash": "sha256-TtCWpdYbUnIM9ydvNn6r3ei+sDqof7+wqXH00t9sCEo=", + "owner": "nix-community", + "repo": "nixpkgs-terraform-providers-bin", + "rev": "752dc0319044c11ca9cff1f8a5839e6e0eb5267d", + "type": "github" + }, + "original": { + "owner": "nix-community", + "repo": "nixpkgs-terraform-providers-bin", + "type": "github" + } + }, + "poetry2nix": { + "inputs": { + "flake-utils": "flake-utils_2", + "nix-github-actions": "nix-github-actions", + "nixpkgs": [ + "nixpkgs" + ] + }, + "locked": { + "lastModified": 1696512612, + "narHash": "sha256-p6niqag7b4XEHvzWgG0X/xjoW/ZXbAxW8ggd8yReT3Y=", + "owner": "nix-community", + "repo": "poetry2nix", + "rev": "e23218d1599e3369dfc878757e58974017e0ecc8", + "type": "github" + }, + "original": { + "owner": "nix-community", + "repo": "poetry2nix", + "type": "github" + } + }, + "root": { + "inputs": { + "flake-utils": "flake-utils", + "nix-filter": "nix-filter", + "nixpkgs": "nixpkgs", + "nixpkgs-terraform-providers-bin": "nixpkgs-terraform-providers-bin", + "poetry2nix": "poetry2nix" + } + }, + "systems": { + "locked": { + "lastModified": 1681028828, + "narHash": "sha256-Vy1rq5AaRuLzOxct8nz4T6wlgyUR7zLU309k9mBC768=", + "owner": "nix-systems", + "repo": "default", + "rev": "da67096a3b9bf56a91d16901293e51ba5b49a27e", + "type": "github" + }, + "original": { + "owner": "nix-systems", + "repo": "default", + "type": "github" + } + }, + "systems_2": { + "locked": { + "lastModified": 1681028828, + "narHash": "sha256-Vy1rq5AaRuLzOxct8nz4T6wlgyUR7zLU309k9mBC768=", + "owner": "nix-systems", + "repo": "default", + "rev": "da67096a3b9bf56a91d16901293e51ba5b49a27e", + "type": "github" + }, + "original": { + "owner": "nix-systems", + "repo": "default", + "type": "github" + } + } + }, + "root": "root", + "version": 7 +} diff --git a/flake.nix b/flake.nix new file mode 100644 index 0000000..814564c --- /dev/null +++ b/flake.nix @@ -0,0 +1,40 @@ +{ + inputs = { + nixpkgs.url = "nixpkgs"; + nix-filter.url = "github:numtide/nix-filter"; + flake-utils.url = "github:numtide/flake-utils"; + nixpkgs-terraform-providers-bin.url = "github:nix-community/nixpkgs-terraform-providers-bin"; + nixpkgs-terraform-providers-bin.inputs.nixpkgs.follows = "nixpkgs"; + poetry2nix = { + url = "github:nix-community/poetry2nix"; + inputs.nixpkgs.follows = "nixpkgs"; + }; + }; + outputs = { + self, + flake-utils, + ... + } @ inputs: + flake-utils.lib.eachDefaultSystem (system: let + pkgs = + import inputs.nixpkgs + { + # config.replaceStdenv = { pkgs, ... }: pkgs.gccMultiStdenv; + inherit system; + }; + in { + # devShells.default = pkgs.mkShell { + # name = "multi-stdenv-gcc"; + # nativeBuildInputs = with pkgs; [pkgsi686Linux.glibc]; + # }; + # devShells.default = pkgs.gccMultiStdenv { + # name = "gcc-test"; + # }; + devShells.default = pkgs.mkShell { + name = "dev"; + buildInputs = with pkgs; [ + bashInteractive + ]; + }; + }); +} diff --git a/labs/archlab/archlab-handout.tar b/labs/archlab/archlab-handout.tar Binary files differnew file mode 100644 index 0000000..979db4e --- /dev/null +++ b/labs/archlab/archlab-handout.tar diff --git a/labs/archlab/archlab.pdf b/labs/archlab/archlab.pdf Binary files differnew file mode 100644 index 0000000..2f1169e --- /dev/null +++ b/labs/archlab/archlab.pdf diff --git a/labs/attacklab/attacklab.pdf b/labs/attacklab/attacklab.pdf Binary files differnew file mode 100644 index 0000000..89f63ea --- /dev/null +++ b/labs/attacklab/attacklab.pdf diff --git a/labs/attacklab/target1.tar b/labs/attacklab/target1.tar Binary files differnew file mode 100644 index 0000000..b72a423 --- /dev/null +++ b/labs/attacklab/target1.tar diff --git a/labs/bomblab/bomb.tar b/labs/bomblab/bomb.tar Binary files differnew file mode 100644 index 0000000..3d38d79 --- /dev/null +++ b/labs/bomblab/bomb.tar diff --git a/labs/bomblab/bomblab.pdf b/labs/bomblab/bomblab.pdf Binary files differnew file mode 100644 index 0000000..e5594f5 --- /dev/null +++ b/labs/bomblab/bomblab.pdf diff --git a/labs/cachelab/cachelab-handout.tar b/labs/cachelab/cachelab-handout.tar Binary files differnew file mode 100644 index 0000000..93c988e --- /dev/null +++ b/labs/cachelab/cachelab-handout.tar diff --git a/labs/cachelab/cachelab.pdf b/labs/cachelab/cachelab.pdf Binary files differnew file mode 100644 index 0000000..b2af686 --- /dev/null +++ b/labs/cachelab/cachelab.pdf diff --git a/labs/datalab/datalab-handout/Driverhdrs.pm b/labs/datalab/datalab-handout/Driverhdrs.pm new file mode 100644 index 0000000..ecf5e2a --- /dev/null +++ b/labs/datalab/datalab-handout/Driverhdrs.pm @@ -0,0 +1,12 @@ +# +# This file contains configuration variables for drivers. +# It was generated by genhdrs.pl. Do not modify it. +# +package Driverhdrs; + +$LAB = "datalab"; +$SERVER_NAME = "changeme.ics.cs.cmu.edu"; +$SERVER_PORT = 8081; +$COURSE_NAME = "csapp"; +$AUTOGRADE_TIMEOUT = 0; +1; diff --git a/labs/datalab/datalab-handout/Driverlib.pm b/labs/datalab/datalab-handout/Driverlib.pm new file mode 100644 index 0000000..d7f7da1 --- /dev/null +++ b/labs/datalab/datalab-handout/Driverlib.pm @@ -0,0 +1,138 @@ +############################################################### +# Driverlib.pm - A package of helper functions for Perl drivers +# +# Copyright (c) 2005 David R. O'Hallaron, All rights reserved. +############################################################### + +package Driverlib; + +use Socket; + +# Autogenerated header file with lab-specific constants +use lib "."; +use Driverhdrs; + +require Exporter; +@ISA = qw(Exporter); +@EXPORT = qw( + driver_post + ); + +use strict; + +##### +# Public functions +# + +# +# driver_post - This is the routine that a driver calls when +# it needs to transmit an autoresult string to the result server. +# +sub driver_post ($$) { + my $userid = shift; # User id for this submission + my $result = shift; # Autoresult string + my $autograded = shift; # Set if called by an autograder + + # Echo the autoresult string to stdout if the driver was called + # by an autograder + if ($autograded) { + print "\n"; + print "AUTORESULT_STRING=$result\n"; + return; + } + + # If the driver was called with a specific userid, then submit + # the autoresult string to the result server over the Internet. + if ($userid) { + my $status = submitr($Driverhdrs::SERVER_NAME, + $Driverhdrs::SERVER_PORT, + $Driverhdrs::COURSE_NAME, + $userid, + $Driverhdrs::LAB, + $result); + + # Print the status of the transfer + if (!($status =~ /OK/)) { + print "$status\n"; + print "Did not send autoresult string to the result server.\n"; + exit(1); + } + print "Success: Sent autoresult string for $userid to the result server.\n"; + } +} + + +##### +# Private functions +# + +# +# submitr - Sends an autoresult string to the result server +# +sub submitr ($$$$$$) { + my $hostname = shift; + my $port = shift; + my $course = shift; + my $userid = shift; + my $lab = shift; + my $result = shift; + + my $internet_addr; + my $enc_result; + my $paddr; + my $line; + my $http_version; + my $errcode; + my $errmsg; + + # Establish the connection to the server + socket(SERVER, PF_INET, SOCK_STREAM, getprotobyname('tcp')); + $internet_addr = inet_aton($hostname) + or die "Could not convert $hostname to an internet address: $!\n"; + $paddr = sockaddr_in($port, $internet_addr); + connect(SERVER, $paddr) + or die "Could not connect to $hostname:$port:$!\n"; + + select((select(SERVER), $| = 1)[0]); # enable command buffering + + # Send HTTP request to server + $enc_result = url_encode($result); + print SERVER "GET /$course/submitr.pl/?userid=$userid&lab=$lab&result=$enc_result&submit=submit HTTP/1.0\r\n\r\n"; + + # Get first HTTP response line + $line = <SERVER>; + chomp($line); + ($http_version, $errcode, $errmsg) = split(/\s+/, $line); + if ($errcode != 200) { + return "Error: HTTP request failed with error $errcode: $errmsg"; + } + + # Read the remaining HTTP response header lines + while ($line = <SERVER>) { + if ($line =~ /^\r\n/) { + last; + } + } + + # Read and return the response from the result server + $line = <SERVER>; + chomp($line); + + close SERVER; + return $line; + +} + +# +# url_encode - Encode text string so it can be included in URI of GET request +# +sub url_encode ($) { + my $value = shift; + + $value =~s/([^a-zA-Z0-9_\-.])/uc sprintf("%%%02x",ord($1))/eg; + return $value; +} + +# Always end a module with a 1 so that it returns TRUE +1; + diff --git a/labs/datalab/datalab-handout/Makefile b/labs/datalab/datalab-handout/Makefile new file mode 100644 index 0000000..ca4bcf0 --- /dev/null +++ b/labs/datalab/datalab-handout/Makefile @@ -0,0 +1,24 @@ +# +# Makefile that builds btest and other helper programs for the CS:APP data lab +# +CC = gcc +CFLAGS = -O -Wall +LIBS = -lm + +all: btest fshow ishow + +btest: btest.c bits.c decl.c tests.c btest.h bits.h + $(CC) $(CFLAGS) $(LIBS) -o btest bits.c btest.c decl.c tests.c + +fshow: fshow.c + $(CC) $(CFLAGS) -o fshow fshow.c + +ishow: ishow.c + $(CC) $(CFLAGS) -o ishow ishow.c + +# Forces a recompile. Used by the driver program. +btestexplicit: + $(CC) $(CFLAGS) $(LIBS) -o btest bits.c btest.c decl.c tests.c + +clean: + rm -f *.o btest fshow ishow *~ diff --git a/labs/datalab/datalab-handout/README b/labs/datalab/datalab-handout/README new file mode 100644 index 0000000..e73d37f --- /dev/null +++ b/labs/datalab/datalab-handout/README @@ -0,0 +1,140 @@ +*********************** +The CS:APP Data Lab +Directions to Students +*********************** + +Your goal is to modify your copy of bits.c so that it passes all the +tests in btest without violating any of the coding guidelines. + + +********* +0. Files: +********* + +Makefile - Makes btest, fshow, and ishow +README - This file +bits.c - The file you will be modifying and handing in +bits.h - Header file +btest.c - The main btest program + btest.h - Used to build btest + decl.c - Used to build btest + tests.c - Used to build btest + tests-header.c- Used to build btest +dlc* - Rule checking compiler binary (data lab compiler) +driver.pl* - Driver program that uses btest and dlc to autograde bits.c +Driverhdrs.pm - Header file for optional "Beat the Prof" contest +fshow.c - Utility for examining floating-point representations +ishow.c - Utility for examining integer representations + +*********************************************************** +1. Modifying bits.c and checking it for compliance with dlc +*********************************************************** + +IMPORTANT: Carefully read the instructions in the bits.c file before +you start. These give the coding rules that you will need to follow if +you want full credit. + +Use the dlc compiler (./dlc) to automatically check your version of +bits.c for compliance with the coding guidelines: + + unix> ./dlc bits.c + +dlc returns silently if there are no problems with your code. +Otherwise it prints messages that flag any problems. Running dlc with +the -e switch: + + unix> ./dlc -e bits.c + +causes dlc to print counts of the number of operators used by each function. + +Once you have a legal solution, you can test it for correctness using +the ./btest program. + +********************* +2. Testing with btest +********************* + +The Makefile in this directory compiles your version of bits.c with +additional code to create a program (or test harness) named btest. + +To compile and run the btest program, type: + + unix> make btest + unix> ./btest [optional cmd line args] + +You will need to recompile btest each time you change your bits.c +program. When moving from one platform to another, you will want to +get rid of the old version of btest and generate a new one. Use the +commands: + + unix> make clean + unix> make btest + +Btest tests your code for correctness by running millions of test +cases on each function. It tests wide swaths around well known corner +cases such as Tmin and zero for integer puzzles, and zero, inf, and +the boundary between denormalized and normalized numbers for floating +point puzzles. When btest detects an error in one of your functions, +it prints out the test that failed, the incorrect result, and the +expected result, and then terminates the testing for that function. + +Here are the command line options for btest: + + unix> ./btest -h + Usage: ./btest [-hg] [-r <n>] [-f <name> [-1|-2|-3 <val>]*] [-T <time limit>] + -1 <val> Specify first function argument + -2 <val> Specify second function argument + -3 <val> Specify third function argument + -f <name> Test only the named function + -g Format output for autograding with no error messages + -h Print this message + -r <n> Give uniform weight of n for all problems + -T <lim> Set timeout limit to lim + +Examples: + + Test all functions for correctness and print out error messages: + unix> ./btest + + Test all functions in a compact form with no error messages: + unix> ./btest -g + + Test function foo for correctness: + unix> ./btest -f foo + + Test function foo for correctness with specific arguments: + unix> ./btest -f foo -1 27 -2 0xf + +Btest does not check your code for compliance with the coding +guidelines. Use dlc to do that. + +******************* +3. Helper Programs +******************* + +We have included the ishow and fshow programs to help you decipher +integer and floating point representations respectively. Each takes a +single decimal or hex number as an argument. To build them type: + + unix> make + +Example usages: + + unix> ./ishow 0x27 + Hex = 0x00000027, Signed = 39, Unsigned = 39 + + unix> ./ishow 27 + Hex = 0x0000001b, Signed = 27, Unsigned = 27 + + unix> ./fshow 0x15213243 + Floating point value 3.255334057e-26 + Bit Representation 0x15213243, sign = 0, exponent = 0x2a, fraction = 0x213243 + Normalized. +1.2593463659 X 2^(-85) + + linux> ./fshow 15213243 + Floating point value 2.131829405e-38 + Bit Representation 0x00e822bb, sign = 0, exponent = 0x01, fraction = 0x6822bb + Normalized. +1.8135598898 X 2^(-126) + + + diff --git a/labs/datalab/datalab-handout/bits.c b/labs/datalab/datalab-handout/bits.c new file mode 100644 index 0000000..3cd1d3d --- /dev/null +++ b/labs/datalab/datalab-handout/bits.c @@ -0,0 +1,360 @@ +/* + * CS:APP Data Lab + * + * <Please put your name and userid here> + * + * bits.c - Source file with your solutions to the Lab. + * This is the file you will hand in to your instructor. + * + * WARNING: Do not include the <stdio.h> header; it confuses the dlc + * compiler. You can still use printf for debugging without including + * <stdio.h>, although you might get a compiler warning. In general, + * it's not good practice to ignore compiler warnings, but in this + * case it's OK. + */ + +#if 0 +/* + * Instructions to Students: + * + * STEP 1: Read the following instructions carefully. + */ + +You will provide your solution to the Data Lab by +editing the collection of functions in this source file. + +INTEGER CODING RULES: + + Replace the "return" statement in each function with one + or more lines of C code that implements the function. Your code + must conform to the following style: + + int Funct(arg1, arg2, ...) { + /* brief description of how your implementation works */ + int var1 = Expr1; + ... + int varM = ExprM; + + varJ = ExprJ; + ... + varN = ExprN; + return ExprR; + } + + Each "Expr" is an expression using ONLY the following: + 1. Integer constants 0 through 255 (0xFF), inclusive. You are + not allowed to use big constants such as 0xffffffff. + 2. Function arguments and local variables (no global variables). + 3. Unary integer operations ! ~ + 4. Binary integer operations & ^ | + << >> + + Some of the problems restrict the set of allowed operators even further. + Each "Expr" may consist of multiple operators. You are not restricted to + one operator per line. + + You are expressly forbidden to: + 1. Use any control constructs such as if, do, while, for, switch, etc. + 2. Define or use any macros. + 3. Define any additional functions in this file. + 4. Call any functions. + 5. Use any other operations, such as &&, ||, -, or ?: + 6. Use any form of casting. + 7. Use any data type other than int. This implies that you + cannot use arrays, structs, or unions. + + + You may assume that your machine: + 1. Uses 2s complement, 32-bit representations of integers. + 2. Performs right shifts arithmetically. + 3. Has unpredictable behavior when shifting if the shift amount + is less than 0 or greater than 31. + + +EXAMPLES OF ACCEPTABLE CODING STYLE: + /* + * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31 + */ + int pow2plus1(int x) { + /* exploit ability of shifts to compute powers of 2 */ + return (1 << x) + 1; + } + + /* + * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31 + */ + int pow2plus4(int x) { + /* exploit ability of shifts to compute powers of 2 */ + int result = (1 << x); + result += 4; + return result; + } + +FLOATING POINT CODING RULES + +For the problems that require you to implement floating-point operations, +the coding rules are less strict. You are allowed to use looping and +conditional control. You are allowed to use both ints and unsigneds. +You can use arbitrary integer and unsigned constants. You can use any arithmetic, +logical, or comparison operations on int or unsigned data. + +You are expressly forbidden to: + 1. Define or use any macros. + 2. Define any additional functions in this file. + 3. Call any functions. + 4. Use any form of casting. + 5. Use any data type other than int or unsigned. This means that you + cannot use arrays, structs, or unions. + 6. Use any floating point data types, operations, or constants. + + +NOTES: + 1. Use the dlc (data lab checker) compiler (described in the handout) to + check the legality of your solutions. + 2. Each function has a maximum number of operations (integer, logical, + or comparison) that you are allowed to use for your implementation + of the function. The max operator count is checked by dlc. + Note that assignment ('=') is not counted; you may use as many of + these as you want without penalty. + 3. Use the btest test harness to check your functions for correctness. + 4. Use the BDD checker to formally verify your functions + 5. The maximum number of ops for each function is given in the + header comment for each function. If there are any inconsistencies + between the maximum ops in the writeup and in this file, consider + this file the authoritative source. + +/* + * STEP 2: Modify the following functions according the coding rules. + * + * IMPORTANT. TO AVOID GRADING SURPRISES: + * 1. Use the dlc compiler to check that your solutions conform + * to the coding rules. + * 2. Use the BDD checker to formally verify that your solutions produce + * the correct answers. + */ + + +#endif +//1 +/* + * bitXor - x^y using only ~ and & + * Example: bitXor(4, 5) = 1 + * Legal ops: ~ & + * Max ops: 14 + * Rating: 1 + */ +int bitXor(int x, int y) { + /* + (x and not y) or (y and not x) <=> + ~(~(x and not y) & ~(y and not x)) + */ + int x_and_not_y = x & ~y; + int y_and_not_x = y & ~x; + int x_not_y_or_y_not_x = ~x_and_not_y & ~y_and_not_x; + return ~x_not_y_or_y_not_x; +} +/* + * tmin - return minimum two's complement integer + * Legal ops: ! ~ & ^ | + << >> + * Max ops: 4 + * Rating: 1 + */ +int tmin(void) { + return 1<<(31); + +} +//2 +/* + * isTmax - returns 1 if x is the maximum, two's complement number, + * and 0 otherwise + * Legal ops: ! ~ & ^ | + + * Max ops: 10 + * Rating: 1 + */ +int isTmax(int x) { + return !!(~0 ^ x) & !(~(x + 1) ^ x); +} +/* + * allOddBits - return 1 if all odd-numbered bits in word set to 1 + * where bits are numbered from 0 (least significant) to 31 (most significant) + * Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1 + * Legal ops: ! ~ & ^ | + << >> + * Max ops: 12 + * Rating: 2 + */ +int allOddBits(int x) { + int odd_bits_mask = 0xAA; + odd_bits_mask |= odd_bits_mask << 16; + odd_bits_mask |= odd_bits_mask << 8; + return !((x & odd_bits_mask) ^ odd_bits_mask); +} +/* + * negate - return -x + * Example: negate(1) = -1. + * Legal ops: ! ~ & ^ | + << >> + * Max ops: 5 + * Rating: 2 + */ +int negate(int x) { + return ~x + 1; +} +//3 +/* + * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9') + * Example: isAsciiDigit(0x35) = 1. + * isAsciiDigit(0x3a) = 0. + * isAsciiDigit(0x05) = 0. + * Legal ops: ! ~ & ^ | + << >> + * Max ops: 15 + * Rating: 3 + */ +int isAsciiDigit(int x) { + int ret = (x + 6) >> 4; + ret &= !(ret ^ 3) & !((x>>4) ^ 3) & !(x>>31); + return ret; +} +/* + * conditional - same as x ? y : z + * Example: conditional(2,4,5) = 4 + * Legal ops: ! ~ & ^ | + << >> + * Max ops: 16 + * Rating: 3 + */ +int conditional(int x, int y, int z) { + /* All ones if x is zero, all zeroes otherwise */ + int mask = (!(x ^ 0) << 31) >> 31; + return (y & ~mask) | (z & mask); +} +/* + * isLessOrEqual - if x <= y then return 1, else return 0 + * Example: isLessOrEqual(4,5) = 1. + * Legal ops: ! ~ & ^ | + << >> + * Max ops: 24 + * Rating: 3 + */ +int isLessOrEqual(int x, int y) { + int int_min = (1<<31); + int x_is_min = !(x ^ int_min); + int x_is_pos = !(x & int_min); + int y_is_pos = !(y & int_min); + + return (!x_is_pos & y_is_pos) + | x_is_min + | !((y + (~x + 1)) & int_min); +} +//4 +/* + * logicalNeg - implement the ! operator, using all of + * the legal operators except ! + * Examples: logicalNeg(3) = 0, logicalNeg(0) = 1 + * Legal ops: ~ & ^ | + << >> + * Max ops: 12 + * Rating: 4 + */ +int logicalNeg(int x) { + /* Using arithmetic shift */ + int sign_bit = x >> 31; + int neg_sign_bit = (~x + 1) >> 31; + return (sign_bit | neg_sign_bit) + 1; + + /* Naive approach */ + /* x |= x>>16; */ + /* x |= x>>8; */ + /* x |= x>>4; */ + /* x |= x>>2; */ + /* x |= x>>1; */ + /* return (x & 1) ^ 1; */ +} +/* howManyBits - return the minimum number of bits required to represent x in + * two's complement + * Examples: howManyBits(12) = 5 + * howManyBits(298) = 10 + * howManyBits(-5) = 4 + * howManyBits(0) = 1 + * howManyBits(-1) = 1 + * howManyBits(0x80000000) = 32 + * Legal ops: ! ~ & ^ | + << >> + * Max ops: 90 + * Rating: 4 + */ +int howManyBits(int x) { + /* My original solution was a lot messier */ + int sign_bit = (x>>31); + int b16, b8, b4, b2, b1, b0; + + /* Take the number that is encoded by the positive bits */ + int u = (x & ~sign_bit) | (~x & sign_bit); + + /* unsigned u = x; */ + /* any greater than 16? */ + /* + 0000 000C + 0000 000C + 0000 000C + 0000 0003 + 0000 0001 + + */ + b16 = (!!(u>>16))<<4; + u >>= b16; + + b8 = (!!(u>>8))<<3; + u >>= b8; + + b4 = (!!(u>>4))<<2; + u >>= b4; + + b2 = (!!(u>>2))<<1; + u >>= b2; + + b1 = (!!(u>>1)); + u >>= b1; + + b0 = !!u; + return b16 + b8 + b4 + b2 + b1 + b0 + 1; +} +//float +/* + * floatScale2 - Return bit-level equivalent of expression 2*f for + * floating point argument f. + * Both the argument and result are passed as unsigned int's, but + * they are to be interpreted as the bit-level representation of + * single-precision floating point values. + * When argument is NaN, return argument + * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while + * Max ops: 30 + * Rating: 4 + */ +unsigned floatScale2(unsigned uf) { + return 2; +} +/* + * floatFloat2Int - Return bit-level equivalent of expression (int) f + * for floating point argument f. + * Argument is passed as unsigned int, but + * it is to be interpreted as the bit-level representation of a + * single-precision floating point value. + * Anything out of range (including NaN and infinity) should return + * 0x80000000u. + * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while + * Max ops: 30 + * Rating: 4 + */ +int floatFloat2Int(unsigned uf) { + return 2; +} +/* + * floatPower2 - Return bit-level equivalent of the expression 2.0^x + * (2.0 raised to the power x) for any 32-bit integer x. + * + * The unsigned value that is returned should have the identical bit + * representation as the single-precision floating-point number 2.0^x. + * If the result is too small to be represented as a denorm, return + * 0. If too large, return +INF. + * + * Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while + * Max ops: 30 + * Rating: 4 + */ +unsigned floatPower2(int x) { + return 2; +} diff --git a/labs/datalab/datalab-handout/bits.h b/labs/datalab/datalab-handout/bits.h new file mode 100644 index 0000000..de2685a --- /dev/null +++ b/labs/datalab/datalab-handout/bits.h @@ -0,0 +1,31 @@ +//1 +int bitXor(int, int); +int test_bitXor(int, int); +int tmin(); +int test_tmin(); +//2 +int isTmax(int); +int test_isTmax(int); +int allOddBits(); +int test_allOddBits(); +int negate(int); +int test_negate(int); +//3 +int isAsciiDigit(int); +int test_isAsciiDigit(int); +int conditional(int, int, int); +int test_conditional(int, int, int); +int isLessOrEqual(int, int); +int test_isLessOrEqual(int, int); +//4 +int logicalNeg(int); +int test_logicalNeg(int); +int howManyBits(int); +int test_howManyBits(int); +//float +unsigned floatScale2(unsigned); +unsigned test_floatScale2(unsigned); +int floatFloat2Int(unsigned); +int test_floatFloat2Int(unsigned); +unsigned floatPower2(int); +unsigned test_floatPower2(int); diff --git a/labs/datalab/datalab-handout/btest.c b/labs/datalab/datalab-handout/btest.c new file mode 100644 index 0000000..660072e --- /dev/null +++ b/labs/datalab/datalab-handout/btest.c @@ -0,0 +1,583 @@ +/* + * CS:APP Data Lab + * + * btest.c - A test harness that checks a student's solution in bits.c + * for correctness. + * + * Copyright (c) 2001-2011, R. Bryant and D. O'Hallaron, All rights + * reserved. May not be used, modified, or copied without permission. + * + * This is an improved version of btest that tests large windows + * around zero and tmin and tmax for integer puzzles, and zero, norm, + * and denorm boundaries for floating point puzzles. + * + * Note: not 64-bit safe. Always compile with gcc -m32 option. + */ +#include <stdio.h> +#include <unistd.h> +#include <stdlib.h> +#include <string.h> +#include <limits.h> +#include <signal.h> +#include <setjmp.h> +#include <math.h> +#include "btest.h" + +/* Not declared in some stdlib.h files, so define here */ +float strtof(const char *nptr, char **endptr); + +/************************* + * Configuration Constants + *************************/ + +/* Handle infinite loops by setting upper limit on execution time, in + seconds */ +#define TIMEOUT_LIMIT 10 + +/* For functions with a single argument, generate TEST_RANGE values + above and below the min and max test values, and above and below + zero. Functions with two or three args will use square and cube + roots of this value, respectively, to avoid combinatorial + explosion */ +#define TEST_RANGE 500000 + +/* This defines the maximum size of any test value array. The + gen_vals() routine creates k test values for each value of + TEST_RANGE, thus MAX_TEST_VALS must be at least k*TEST_RANGE */ +#define MAX_TEST_VALS 13*TEST_RANGE + +/********************************** + * Globals defined in other modules + **********************************/ +/* This characterizes the set of puzzles to test. + Defined in decl.c and generated from templates in ./puzzles dir */ +extern test_rec test_set[]; + +/************************************************ + * Write-once globals defined by command line args + ************************************************/ + +/* Emit results in a format for autograding, without showing + and counter-examples */ +static int grade = 0; + +/* Time out after this number of seconds */ +static int timeout_limit = TIMEOUT_LIMIT; /* -T */ + +/* If non-NULL, test only one function (-f) */ +static char* test_fname = NULL; + +/* Special case when only use fixed argument(s) (-1, -2, or -3) */ +static int has_arg[3] = {0,0,0}; +static unsigned argval[3] = {0,0,0}; + +/* Use fixed weight for rating, and if so, what should it be? (-r) */ +static int global_rating = 0; + +/****************** + * Helper functions + ******************/ + +/* + * Signal - installs a signal handler + */ +typedef void handler_t(int); + +handler_t *Signal(int signum, handler_t *handler) +{ + struct sigaction action, old_action; + + action.sa_handler = handler; + sigemptyset(&action.sa_mask); /* block sigs of type being handled */ + action.sa_flags = SA_RESTART; /* restart syscalls if possible */ + + if (sigaction(signum, &action, &old_action) < 0) + perror("Signal error"); + return (old_action.sa_handler); +} + +/* + * timeout_handler - SIGALARM hander + */ +sigjmp_buf envbuf; +void timeout_handler(int sig) { + siglongjmp(envbuf, 1); +} + +/* + * random_val - Return random integer value between min and max + */ +static int random_val(int min, int max) +{ + double weight = rand()/(double) RAND_MAX; + int result = min * (1-weight) + max * weight; + return result; +} + +/* + * gen_vals - Generate the integer values we'll use to test a function + */ +static int gen_vals(int test_vals[], int min, int max, int test_range, int arg) +{ + int i; + int test_count = 0; + + /* Special case: If the user has specified a specific function + argument using the -1, -2, or -3 flags, then simply use this + argument and return */ + if (has_arg[arg]) { + test_vals[0] = argval[arg]; + return 1; + } + + /* + * Special case: Generate test vals for floating point functions + * where the input argument is an unsigned bit-level + * representation of a float. For this case we want to test the + * regions around zero, the smallest normalized and largest + * denormalized numbers, one, and the largest normalized number, + * as well as inf and nan. + */ + if ((min == 1 && max == 1)) { + unsigned smallest_norm = 0x00800000; + unsigned one = 0x3f800000; + unsigned largest_norm = 0x7f000000; + + unsigned inf = 0x7f800000; + unsigned nan = 0x7fc00000; + unsigned sign = 0x80000000; + + /* Test range should be at most 1/2 the range of one exponent + value */ + if (test_range > (1 << 23)) { + test_range = 1 << 23; + } + + /* Functions where the input argument is an unsigned bit-level + representation of a float. The number of tests generated + inside this loop body is the value k referenced in the + comment for the global variable MAX_TEST_VALS. */ + + for (i = 0; i < test_range; i++) { + /* Denorms around zero */ + test_vals[test_count++] = i; + test_vals[test_count++] = sign | i; + + /* Region around norm to denorm transition */ + test_vals[test_count++] = smallest_norm + i; + test_vals[test_count++] = smallest_norm - i; + test_vals[test_count++] = sign | (smallest_norm + i); + test_vals[test_count++] = sign | (smallest_norm - i); + + /* Region around one */ + test_vals[test_count++] = one + i; + test_vals[test_count++] = one - i; + test_vals[test_count++] = sign | (one + i); + test_vals[test_count++] = sign | (one - i); + + /* Region below largest norm */ + test_vals[test_count++] = largest_norm - i; + test_vals[test_count++] = sign | (largest_norm - i); + } + + /* special vals */ + test_vals[test_count++] = inf; /* inf */ + test_vals[test_count++] = sign | inf; /* -inf */ + test_vals[test_count++] = nan; /* nan */ + test_vals[test_count++] = sign | nan; /* -nan */ + + return test_count; + } + + + /* + * Normal case: Generate test vals for integer functions + */ + + /* If the range is small enough, then do exhaustively */ + if (max - MAX_TEST_VALS <= min) { + for (i = min; i <= max; i++) + test_vals[test_count++] = i; + return test_count; + } + + /* Otherwise, need to sample. Do so near the boundaries, around + zero, and for some random cases. */ + for (i = 0; i < test_range; i++) { + + /* Test around the boundaries */ + test_vals[test_count++] = min + i; + test_vals[test_count++] = max - i; + + /* If zero falls between min and max, then also test around zero */ + if (i >= min && i <= max) + test_vals[test_count++] = i; + if (-i >= min && -i <= max) + test_vals[test_count++] = -i; + + /* Random case between min and max */ + test_vals[test_count++] = random_val(min, max); + + } + return test_count; +} + +/* + * test_0_arg - Test a function with zero arguments + */ +static int test_0_arg(funct_t f, funct_t ft, char *name) +{ + int r = f(); + int rt = ft(); + int error = (r != rt); + + if (error && !grade) + printf("ERROR: Test %s() failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, r, r, rt, rt); + + return error; +} + +/* + * test_1_arg - Test a function with one argument + */ +static int test_1_arg(funct_t f, funct_t ft, int arg1, char *name) +{ + funct1_t f1 = (funct1_t) f; + funct1_t f1t = (funct1_t) ft; + int r, rt, error; + + r = f1(arg1); + rt = f1t(arg1); + error = (r != rt); + if (error && !grade) + printf("ERROR: Test %s(%d[0x%x]) failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, arg1, arg1, r, r, rt, rt); + + return error; +} + +/* + * test_2_arg - Test a function with two arguments + */ +static int test_2_arg(funct_t f, funct_t ft, int arg1, int arg2, char *name) +{ + funct2_t f2 = (funct2_t) f; + funct2_t f2t = (funct2_t) ft; + int r = f2(arg1, arg2); + int rt = f2t(arg1, arg2); + int error = (r != rt); + + if (error && !grade) + printf("ERROR: Test %s(%d[0x%x],%d[0x%x]) failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, arg1, arg1, arg2, arg2, r, r, rt, rt); + + return error; +} + +/* + * test_3_arg - Test a function with three arguments + */ +static int test_3_arg(funct_t f, funct_t ft, + int arg1, int arg2, int arg3, char *name) +{ + funct3_t f3 = (funct3_t) f; + funct3_t f3t = (funct3_t) ft; + int r = f3(arg1, arg2, arg3); + int rt = f3t(arg1, arg2, arg3); + int error = (r != rt); + + if (error && !grade) + printf("ERROR: Test %s(%d[0x%x],%d[0x%x],%d[0x%x]) failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, arg1, arg1, arg2, arg2, arg3, arg3, r, r, rt, rt); + + return error; +} + +/* + * test_function - Test a function. Return number of errors + */ +static int test_function(test_ptr t) { + int test_counts[3]; /* number of test values for each arg */ + int args = t->args; /* number of function arguments */ + int arg_test_range[3]; /* test range for each argument */ + int i, a1, a2, a3; + int errors = 0; + + /* These are the test values for each arg. Declared with the + static attribute so that the array will be allocated in bss + rather than the stack */ + static int arg_test_vals[3][MAX_TEST_VALS]; + + /* Sanity check on the number of args */ + if (args < 0 || args > 3) { + printf("Configuration error: invalid number of args (%d) for function %s\n", args, t->name); + exit(1); + } + + /* Assign range of argument test vals so as to conserve the total + number of tests, independent of the number of arguments */ + if (args == 1) { + arg_test_range[0] = TEST_RANGE; + } + else if (args == 2) { + arg_test_range[0] = pow((double)TEST_RANGE, 0.5); /* sqrt */ + arg_test_range[1] = arg_test_range[0]; + } + else { + arg_test_range[0] = pow((double)TEST_RANGE, 0.333); /* cbrt */ + arg_test_range[1] = arg_test_range[0]; + arg_test_range[2] = arg_test_range[0]; + } + + /* Sanity check on the ranges */ + if (arg_test_range[0] < 1) + arg_test_range[0] = 1; + if (arg_test_range[1] < 1) + arg_test_range[1] = 1; + if (arg_test_range[2] < 1) + arg_test_range[2] = 1; + + /* Create a test set for each argument */ + for (i = 0; i < args; i++) { + test_counts[i] = gen_vals(arg_test_vals[i], + t->arg_ranges[i][0], /* min */ + t->arg_ranges[i][1], /* max */ + arg_test_range[i], + i); + + } + + /* Handle timeouts in the test code */ + if (timeout_limit > 0) { + int rc; + rc = sigsetjmp(envbuf, 1); + if (rc) { + /* control will reach here if there is a timeout */ + errors = 1; + printf("ERROR: Test %s failed.\n Timed out after %d secs (probably infinite loop)\n", t->name, timeout_limit); + return errors; + } + alarm(timeout_limit); + } + + + /* Test function has no arguments */ + if (args == 0) { + errors += test_0_arg(t->solution_funct, t->test_funct, t->name); + return errors; + } + + /* + * Test function has at least one argument + */ + + /* Iterate over the values for first argument */ + + for (a1 = 0; a1 < test_counts[0]; a1++) { + if (args == 1) { + errors += test_1_arg(t->solution_funct, + t->test_funct, + arg_test_vals[0][a1], + t->name); + + /* Stop testing if there is an error */ + if (errors) + return errors; + } + else { + /* if necessary, iterate over values for second argument */ + for (a2 = 0; a2 < test_counts[1]; a2++) { + if (args == 2) { + errors += test_2_arg(t->solution_funct, + t->test_funct, + arg_test_vals[0][a1], + arg_test_vals[1][a2], + t->name); + + /* Stop testing if there is an error */ + if (errors) + return errors; + } + else { + /* if necessary, iterate over vals for third arg */ + for (a3 = 0; a3 < test_counts[2]; a3++) { + errors += test_3_arg(t->solution_funct, + t->test_funct, + arg_test_vals[0][a1], + arg_test_vals[1][a2], + arg_test_vals[2][a3], + t->name); + + /* Stop testing if there is an error */ + if (errors) + return errors; + } /* a3 */ + } + } /* a2 */ + } + } /* a1 */ + + + return errors; +} + +/* + * run_tests - Run series of tests. Return number of errors + */ +static int run_tests() +{ + int i; + int errors = 0; + double points = 0.0; + double max_points = 0.0; + + printf("Score\tRating\tErrors\tFunction\n"); + + for (i = 0; test_set[i].solution_funct; i++) { + int terrors; + double tscore; + double tpoints; + if (!test_fname || strcmp(test_set[i].name,test_fname) == 0) { + int rating = global_rating ? global_rating : test_set[i].rating; + terrors = test_function(&test_set[i]); + errors += terrors; + tscore = terrors == 0 ? 1.0 : 0.0; + tpoints = rating * tscore; + points += tpoints; + max_points += rating; + + if (grade || terrors < 1) + printf(" %.0f\t%d\t%d\t%s\n", + tpoints, rating, terrors, test_set[i].name); + + } + } + + printf("Total points: %.0f/%.0f\n", points, max_points); + return errors; +} + +/* + * get_num_val - Extract hex/decimal/or float value from string + */ +static int get_num_val(char *sval, unsigned *valp) { + char *endp; + + /* See if it's an integer or floating point */ + int ishex = 0; + int isfloat = 0; + int i; + for (i = 0; sval[i]; i++) { + switch (sval[i]) { + case 'x': + case 'X': + ishex = 1; + break; + case 'e': + case 'E': + if (!ishex) + isfloat = 1; + break; + case '.': + isfloat = 1; + break; + default: + break; + } + } + if (isfloat) { + float fval = strtof(sval, &endp); + if (!*endp) { + *valp = *(unsigned *) &fval; + return 1; + } + return 0; + } else { + long long int llval = strtoll(sval, &endp, 0); + long long int upperbits = llval >> 31; + /* will give -1 for negative, 0 or 1 for positive */ + if (!*valp && (upperbits == 0 || upperbits == -1 || upperbits == 1)) { + *valp = (unsigned) llval; + return 1; + } + return 0; + } +} + + +/* + * usage - Display usage info + */ +static void usage(char *cmd) { + printf("Usage: %s [-hg] [-r <n>] [-f <name> [-1|-2|-3 <val>]*] [-T <time limit>]\n", cmd); + printf(" -1 <val> Specify first function argument\n"); + printf(" -2 <val> Specify second function argument\n"); + printf(" -3 <val> Specify third function argument\n"); + printf(" -f <name> Test only the named function\n"); + printf(" -g Compact output for grading (with no error msgs)\n"); + printf(" -h Print this message\n"); + printf(" -r <n> Give uniform weight of n for all problems\n"); + printf(" -T <lim> Set timeout limit to lim\n"); + exit(1); +} + + +/************** + * Main routine + **************/ + +int main(int argc, char *argv[]) +{ + char c; + + /* parse command line args */ + while ((c = getopt(argc, argv, "hgf:r:T:1:2:3:")) != -1) + switch (c) { + case 'h': /* help */ + usage(argv[0]); + break; + case 'g': /* grading option for autograder */ + grade = 1; + break; + case 'f': /* test only one function */ + test_fname = strdup(optarg); + break; + case 'r': /* set global rating for each problem */ + global_rating = atoi(optarg); + if (global_rating < 0) + usage(argv[0]); + break; + case '1': /* Get first argument */ + has_arg[0] = get_num_val(optarg, &argval[0]); + if (!has_arg[0]) { + printf("Bad argument '%s'\n", optarg); + exit(0); + } + break; + case '2': /* Get first argument */ + has_arg[1] = get_num_val(optarg, &argval[1]); + if (!has_arg[1]) { + printf("Bad argument '%s'\n", optarg); + exit(0); + } + break; + case '3': /* Get first argument */ + has_arg[2] = get_num_val(optarg, &argval[2]); + if (!has_arg[2]) { + printf("Bad argument '%s'\n", optarg); + exit(0); + } + break; + case 'T': /* Set timeout limit */ + timeout_limit = atoi(optarg); + break; + default: + usage(argv[0]); + } + + if (timeout_limit > 0) { + Signal(SIGALRM, timeout_handler); + } + + /* test each function */ + run_tests(); + + return 0; +} diff --git a/labs/datalab/datalab-handout/btest.h b/labs/datalab/datalab-handout/btest.h new file mode 100644 index 0000000..a011bc1 --- /dev/null +++ b/labs/datalab/datalab-handout/btest.h @@ -0,0 +1,32 @@ +/* + * CS:APP Data Lab + */ + +/* Declare different function types */ +typedef int (*funct_t) (void); +typedef int (*funct1_t)(int); +typedef int (*funct2_t)(int, int); +typedef int (*funct3_t)(int, int, int); + +/* Combine all the information about a function and its tests as structure */ +typedef struct { + char *name; /* String name */ + funct_t solution_funct; /* Function */ + funct_t test_funct; /* Test function */ + int args; /* Number of function arguments */ + char *ops; /* List of legal operators. Special case: "$" for floating point */ + int op_limit; /* Max number of ops allowed in solution */ + int rating; /* Problem rating (1 -- 4) */ + int arg_ranges[3][2]; /* Argument ranges. Always defined for 3 args, even if */ + /* the function takes fewer. Special case: First arg */ + /* must be set to {1,1} for f.p. puzzles */ +} test_rec, *test_ptr; + +extern test_rec test_set[]; + + + + + + + diff --git a/labs/datalab/datalab-handout/decl.c b/labs/datalab/datalab-handout/decl.c new file mode 100644 index 0000000..11370c7 --- /dev/null +++ b/labs/datalab/datalab-handout/decl.c @@ -0,0 +1,57 @@ +#include <stdio.h> +#include <stdlib.h> +#include <limits.h> + +#define TMin INT_MIN +#define TMax INT_MAX + +#include "btest.h" +#include "bits.h" + +test_rec test_set[] = { +//1 + + + + + {"bitXor", (funct_t) bitXor, (funct_t) test_bitXor, 2, "& ~", 14, 1, + {{TMin, TMax},{TMin,TMax},{TMin,TMax}}}, + {"tmin", (funct_t) tmin, (funct_t) test_tmin, 0, "! ~ & ^ | + << >>", 4, 1, + {{TMin, TMax},{TMin,TMax},{TMin,TMax}}}, +//2 + {"isTmax", (funct_t) isTmax, (funct_t) test_isTmax, 1, "! ~ & ^ | +", 10, 1, + {{TMin, TMax},{TMin,TMax},{TMin,TMax}}}, + {"allOddBits", (funct_t) allOddBits, (funct_t) test_allOddBits, 1, + "! ~ & ^ | + << >>", 12, 2, + {{TMin, TMax},{TMin,TMax},{TMin,TMax}}}, + {"negate", (funct_t) negate, (funct_t) test_negate, 1, + "! ~ & ^ | + << >>", 5, 2, + {{TMin, TMax},{TMin,TMax},{TMin,TMax}}}, +//3 + {"isAsciiDigit", (funct_t) isAsciiDigit, (funct_t) test_isAsciiDigit, 1, + "! ~ & ^ | + << >>", 15, 3, + {{TMin, TMax},{TMin,TMax},{TMin,TMax}}}, + {"conditional", (funct_t) conditional, (funct_t) test_conditional, 3, "! ~ & ^ | << >>", 16, 3, + {{TMin, TMax},{TMin,TMax},{TMin,TMax}}}, + {"isLessOrEqual", (funct_t) isLessOrEqual, (funct_t) test_isLessOrEqual, 2, + "! ~ & ^ | + << >>", 24, 3, + {{TMin, TMax},{TMin,TMax},{TMin,TMax}}}, +//4 + {"logicalNeg", (funct_t) logicalNeg, (funct_t) test_logicalNeg, 1, + "~ & ^ | + << >>", 12, 4, + {{TMin, TMax},{TMin,TMax},{TMin,TMax}}}, + {"howManyBits", (funct_t) howManyBits, (funct_t) test_howManyBits, 1, "! ~ & ^ | + << >>", 90, 4, + {{TMin, TMax},{TMin,TMax},{TMin,TMax}}}, +//float + {"floatScale2", (funct_t) floatScale2, (funct_t) test_floatScale2, 1, + "$", 30, 4, + {{1, 1},{1,1},{1,1}}}, + {"floatFloat2Int", (funct_t) floatFloat2Int, (funct_t) test_floatFloat2Int, 1, + "$", 30, 4, + {{1, 1},{1,1},{1,1}}}, + {"floatPower2", (funct_t) floatPower2, (funct_t) test_floatPower2, 1, + "$", 30, 4, + {{1, 1},{1,1},{1,1}}}, + {"", NULL, NULL, 0, "", 0, 0, + {{0, 0},{0,0},{0,0}}} +}; diff --git a/labs/datalab/datalab-handout/driver.pl b/labs/datalab/datalab-handout/driver.pl new file mode 100755 index 0000000..143c440 --- /dev/null +++ b/labs/datalab/datalab-handout/driver.pl @@ -0,0 +1,439 @@ +#!/usr/bin/perl +####################################################################### +# driver.pl - CS:APP Data Lab driver +# +# Copyright (c) 2004-2011, R. Bryant and D. O'Hallaron, All rights +# reserved. May not be used, modified, or copied without permission. +# +# Note: The driver can use either btest or the BDD checker to check +# puzzles for correctness. This version of the lab uses btest, which +# has been extended to do better testing of both integer and +# floating-point puzzles. +# +####################################################################### + +use strict 'vars'; +use Getopt::Std; + +use lib "."; +use Driverlib; + +# Set to 1 to use btest, 0 to use the BDD checker. +my $USE_BTEST = 1; + +# Generic settings +$| = 1; # Flush stdout each time +umask(0077); # Files created by the user in tmp readable only by that user +$ENV{PATH} = "/usr/local/bin:/usr/bin:/bin"; + +# +# usage - print help message and terminate +# +sub usage { + printf STDERR "$_[0]\n"; + printf STDERR "Usage: $0 [-h] [-u \"nickname\"]\n"; + printf STDERR "Options:\n"; + printf STDERR " -h Print this message.\n"; + printf STDERR " -u \"nickname\" Send autoresult to server, using nickname on scoreboard)\n"; + die "\n"; +} + +############## +# Main routine +############## +my $login = getlogin() || (getpwuid($<))[0] || "unknown"; +my $tmpdir = "/var/tmp/datalab.$login.$$"; +my $diemsg = "The files are in $tmpdir."; + +my $driverfiles; +my $infile; +my $autograded; + +my $status; +my $inpuzzles; +my $puzzlecnt; +my $line; +my $blank; +my $name; +my $c_points; +my $c_rating; +my $c_errors; +my $p_points; +my $p_rating; +my $p_errors; +my $total_c_points; +my $total_c_rating; +my $total_p_points; +my $total_p_rating; +my $tops; +my $tpoints; +my $trating; +my $foo; +my $name; +my $msg; +my $nickname; +my $autoresult; + +my %puzzle_c_points; +my %puzzle_c_rating; +my %puzzle_c_errors; +my %puzzle_p_points; +my %puzzle_p_ops; +my %puzzle_p_maxops; +my %puzzle_number; + + +# Parse the command line arguments +no strict; +getopts('hu:f:A'); +if ($opt_h) { + usage(); +} + +# The default input file is bits.c (change with -f) +$infile = "bits.c"; +$nickname = ""; + +##### +# These are command line args that every driver must support +# + +# Causes the driver to send an autoresult to the server on behalf of user +if ($opt_u) { + $nickname = $opt_u; + check_nickname($nickname); +} + +# Hidden flag that indicates that the driver was invoked by an autograder +if ($opt_A) { + $autograded = $opt_A; +} + +##### +# Drivers can also define an arbitary number of other command line args +# +# Optional hidden flag used by the autograder +if ($opt_f) { + $infile = $opt_f; +} + +use strict 'vars'; + +################################################ +# Compute the correctness and performance scores +################################################ + +# Make sure that an executable dlc (data lab compiler) exists +(-e "./dlc" and -x "./dlc") + or die "$0: ERROR: No executable dlc binary.\n"; + + +# If using the bdd checker, then make sure it exists +if (!$USE_BTEST) { + (-e "./bddcheck/cbit/cbit" and -x "./bddcheck/cbit/cbit") + or die "$0: ERROR: No executable cbit binary.\n"; +} + +# +# Set up the contents of the scratch directory +# +system("mkdir $tmpdir") == 0 + or die "$0: Could not make scratch directory $tmpdir.\n"; + +# Copy the student's work to the scratch directory +unless (system("cp $infile $tmpdir/bits.c") == 0) { + clean($tmpdir); + die "$0: Could not copy file $infile to scratch directory $tmpdir.\n"; +} + +# Copy the various autograding files to the scratch directory +if ($USE_BTEST) { + $driverfiles = "Makefile dlc btest.c decl.c tests.c btest.h bits.h"; + unless (system("cp -r $driverfiles $tmpdir") == 0) { + clean($tmpdir); + die "$0: Could not copy autogradingfiles to $tmpdir.\n"; + } +} +else { + $driverfiles = "dlc tests.c bddcheck"; + unless (system("cp -r $driverfiles $tmpdir") == 0) { + clean($tmpdir); + die "$0: Could not copy support files to $tmpdir.\n"; + } +} + +# Change the current working directory to the scratch directory +unless (chdir($tmpdir)) { + clean($tmpdir); + die "$0: Could not change directory to $tmpdir.\n"; +} + +# +# Generate a zapped (for coding rules) version of bits.c. In this +# zapped version of bits.c, any functions with illegal operators are +# transformed to have empty function bodies. +# +print "1. Running './dlc -z' to identify coding rules violations.\n"; +system("cp bits.c save-bits.c") == 0 + or die "$0: ERROR: Could not create backup copy of bits.c. $diemsg\n"; +system("./dlc -z -o zap-bits.c bits.c") == 0 + or die "$0: ERROR: zapped bits.c did not compile. $diemsg\n"; + +# +# Run btest or BDD checker to determine correctness score +# +if ($USE_BTEST) { + print "\n2. Compiling and running './btest -g' to determine correctness score.\n"; + system("cp zap-bits.c bits.c"); + + # Compile btest + system("make btestexplicit") == 0 + or die "$0: Could not make btest in $tmpdir. $diemsg\n"; + + # Run btest + $status = system("./btest -g > btest-zapped.out 2>&1"); + if ($status != 0) { + die "$0: ERROR: btest check failed. $diemsg\n"; + } +} +else { + print "\n2. Running './bddcheck/check.pl -g' to determine correctness score.\n"; + system("cp zap-bits.c bits.c"); + $status = system("./bddcheck/check.pl -g > btest-zapped.out 2>&1"); + if ($status != 0) { + die "$0: ERROR: BDD check failed. $diemsg\n"; + } +} + +# +# Run dlc to identify operator count violations. +# +print "\n3. Running './dlc -Z' to identify operator count violations.\n"; +system("./dlc -Z -o Zap-bits.c save-bits.c") == 0 + or die "$0: ERROR: dlc unable to generated Zapped bits.c file.\n"; + +# +# Run btest or the bdd checker to compute performance score +# +if ($USE_BTEST) { + print "\n4. Compiling and running './btest -g -r 2' to determine performance score.\n"; + system("cp Zap-bits.c bits.c"); + + # Compile btest + system("make btestexplicit") == 0 + or die "$0: Could not make btest in $tmpdir. $diemsg\n"; + print "\n"; + + # Run btest + $status = system("./btest -g -r 2 > btest-Zapped.out 2>&1"); + if ($status != 0) { + die "$0: ERROR: Zapped btest failed. $diemsg\n"; + } +} +else { + print "\n4. Running './bddcheck/check.pl -g -r 2' to determine performance score.\n"; + system("cp Zap-bits.c bits.c"); + $status = system("./bddcheck/check.pl -g -r 2 > btest-Zapped.out 2>&1"); + if ($status != 0) { + die "$0: ERROR: Zapped bdd checker failed. $diemsg\n"; + } +} + +# +# Run dlc to get the operator counts on the zapped input file +# +print "\n5. Running './dlc -e' to get operator count of each function.\n"; +$status = system("./dlc -W1 -e zap-bits.c > dlc-opcount.out 2>&1"); +if ($status != 0) { + die "$0: ERROR: bits.c did not compile. $diemsg\n"; +} + +################################################################# +# Collect the correctness and performance results for each puzzle +################################################################# + +# +# Collect the correctness results +# +%puzzle_c_points = (); # Correctness score computed by btest +%puzzle_c_errors = (); # Correctness error discovered by btest +%puzzle_c_rating = (); # Correctness puzzle rating (max points) + +$inpuzzles = 0; # Becomes true when we start reading puzzle results +$puzzlecnt = 0; # Each puzzle gets a unique number +$total_c_points = 0; +$total_c_rating = 0; + +open(INFILE, "$tmpdir/btest-zapped.out") + or die "$0: ERROR: could not open input file $tmpdir/btest-zapped.out\n"; + +while ($line = <INFILE>) { + chomp($line); + + # Notice that we're ready to read the puzzle scores + if ($line =~ /^Score/) { + $inpuzzles = 1; + next; + } + + # Notice that we're through reading the puzzle scores + if ($line =~ /^Total/) { + $inpuzzles = 0; + next; + } + + # Read and record a puzzle's name and score + if ($inpuzzles) { + ($blank, $c_points, $c_rating, $c_errors, $name) = split(/\s+/, $line); + $puzzle_c_points{$name} = $c_points; + $puzzle_c_errors{$name} = $c_errors; + $puzzle_c_rating{$name} = $c_rating; + $puzzle_number{$name} = $puzzlecnt++; + $total_c_points += $c_points; + $total_c_rating += $c_rating; + } + +} +close(INFILE); + +# +# Collect the performance results +# +%puzzle_p_points = (); # Performance points + +$inpuzzles = 0; # Becomes true when we start reading puzzle results +$total_p_points = 0; +$total_p_rating = 0; + +open(INFILE, "$tmpdir/btest-Zapped.out") + or die "$0: ERROR: could not open input file $tmpdir/btest-Zapped.out\n"; + +while ($line = <INFILE>) { + chomp($line); + + # Notice that we're ready to read the puzzle scores + if ($line =~ /^Score/) { + $inpuzzles = 1; + next; + } + + # Notice that we're through reading the puzzle scores + if ($line =~ /^Total/) { + $inpuzzles = 0; + next; + } + + # Read and record a puzzle's name and score + if ($inpuzzles) { + ($blank, $p_points, $p_rating, $p_errors, $name) = split(/\s+/, $line); + $puzzle_p_points{$name} = $p_points; + $total_p_points += $p_points; + $total_p_rating += $p_rating; + } +} +close(INFILE); + +# +# Collect the operator counts generated by dlc +# +open(INFILE, "$tmpdir/dlc-opcount.out") + or die "$0: ERROR: could not open input file $tmpdir/dlc-opcount.out\n"; + +$tops = 0; +while ($line = <INFILE>) { + chomp($line); + + if ($line =~ /(\d+) operators/) { + ($foo, $foo, $foo, $name, $msg) = split(/:/, $line); + $puzzle_p_ops{$name} = $1; + $tops += $1; + } +} +close(INFILE); + +# +# Print a table of results sorted by puzzle number +# +print "\n"; +printf("%s\t%s\n", "Correctness Results", "Perf Results"); +printf("%s\t%s\t%s\t%s\t%s\t%s\n", "Points", "Rating", "Errors", + "Points", "Ops", "Puzzle"); +foreach $name (sort {$puzzle_number{$a} <=> $puzzle_number{$b}} + keys %puzzle_number) { + printf("%d\t%d\t%d\t%d\t%d\t\%s\n", + $puzzle_c_points{$name}, + $puzzle_c_rating{$name}, + $puzzle_c_errors{$name}, + $puzzle_p_points{$name}, + $puzzle_p_ops{$name}, + $name); +} + +$tpoints = $total_c_points + $total_p_points; +$trating = $total_c_rating + $total_p_rating; + +print "\nScore = $tpoints/$trating [$total_c_points/$total_c_rating Corr + $total_p_points/$total_p_rating Perf] ($tops total operators)\n"; + +# +# Optionally send the autoresult to the contest server if the driver +# was called with the -u command line flag. +# +if ($nickname) { + # Generate the autoresult + $autoresult = "$tpoints|$total_c_points|$total_p_points|$tops"; + foreach $name (sort {$puzzle_number{$a} <=> $puzzle_number{$b}} + keys %puzzle_number) { + $autoresult .= " |$name:$puzzle_c_points{$name}:$puzzle_c_rating{$name}:$puzzle_p_points{$name}:$puzzle_p_ops{$name}"; + } + + # Post the autoresult to the server. The Linux login id is + # concatenated with the user-supplied nickname for some (very) loose + # authentication of submissions. + &Driverlib::driver_post("$login:$nickname", $autoresult, $autograded); +} + +# Clean up and exit +clean ($tmpdir); +exit; + +################## +# Helper functions +# + +# +# check_nickname - Check a nickname for legality +# +sub check_nickname { + my $nickname = shift; + + # Nicknames can't be empty + if (length($nickname) < 1) { + die "$0: Error: Empty nickname.\n"; + } + + # Nicknames can't be too long + if (length($nickname) > 35) { + die "$0: Error: Nickname exceeds 35 characters.\n"; + } + + # Nicknames can have restricted set of metacharacters (e.g., no # + # HTML tags) + if (!($nickname =~ /^[_-\w.,'@ ]+$/)) { + die "$0: Error: Illegal character in nickname. Only alphanumerics, apostrophes, commas, periods, dashes, underscores, and ampersands are allowed.\n"; + } + + # Nicknames can't be all whitespace + if ($nickname =~ /^\s*$/) { + die "$0: Error: Nickname is all whitespace.\n"; + } + +} + +# +# clean - remove the scratch directory +# +sub clean { + my $tmpdir = shift; + system("rm -rf $tmpdir"); +} + diff --git a/labs/datalab/datalab-handout/fshow.c b/labs/datalab/datalab-handout/fshow.c new file mode 100644 index 0000000..fc918f6 --- /dev/null +++ b/labs/datalab/datalab-handout/fshow.c @@ -0,0 +1,151 @@ +/* Display structure of floating-point numbers */ + +#include <stdio.h> +#include <stdlib.h> +float strtof(const char *nptr, char **endptr); + +#define FLOAT_SIZE 32 +#define FRAC_SIZE 23 +#define EXP_SIZE 8 +#define BIAS ((1<<(EXP_SIZE-1))-1) +#define FRAC_MASK ((1<<FRAC_SIZE)-1) +#define EXP_MASK ((1<<EXP_SIZE)-1) + +/* Floating point helpers */ +unsigned f2u(float f) +{ + union { + unsigned u; + float f; + } v; + v.u = 0; + v.f = f; + return v.u; +} + +static float u2f(unsigned u) +{ + union { + unsigned u; + float f; + } v; + v.u = u; + return v.f; +} + +/* Get exponent */ +unsigned get_exp(unsigned uf) +{ + return (uf>>FRAC_SIZE) & EXP_MASK; +} + +/* Get fraction */ +unsigned get_frac(unsigned uf) +{ + return uf & FRAC_MASK; +} + +/* Get sign */ +unsigned get_sign(unsigned uf) +{ + return (uf>>(FLOAT_SIZE-1)) & 0x1; +} + +void show_float(unsigned uf) +{ + float f = u2f(uf); + unsigned exp = get_exp(uf); + unsigned frac = get_frac(uf); + unsigned sign = get_sign(uf); + + printf("\nFloating point value %.10g\n", f); + printf("Bit Representation 0x%.8x, sign = %x, exponent = 0x%.2x, fraction = 0x%.6x\n", + uf, sign, exp, frac); + if (exp == EXP_MASK) { + if (frac == 0) { + printf("%cInfinity\n", sign ? '-' : '+'); + } else + printf("Not-A-Number\n"); + } else { + int denorm = (exp == 0); + int uexp = denorm ? 1-BIAS : exp - BIAS; + int mantissa = denorm ? frac : frac + (1<<FRAC_SIZE); + float fman = (float) mantissa / (float) (1<<FRAC_SIZE); + printf("%s. %c%.10f X 2^(%d)\n", + denorm ? "Denormalized" : "Normalized", + sign ? '-' : '+', + fman, uexp); + } +} + +/* Extract hex/decimal/or float value from string */ +static int get_num_val(char *sval, unsigned *valp) { + char *endp; + /* See if it's an integer or floating point */ + int ishex = 0; + int isfloat = 0; + int i; + for (i = 0; sval[i]; i++) { + switch (sval[i]) { + case 'x': + case 'X': + ishex = 1; + break; + case 'e': + case 'E': + if (!ishex) + isfloat = 1; + break; + case '.': + isfloat = 1; + break; + default: + break; + } + } + if (isfloat) { + float fval = strtof(sval, &endp); + if (!*endp) { + *valp = *(unsigned *) &fval; + return 1; + } + return 0; + } else { + long long int llval = strtoll(sval, &endp, 0); + long long int upperbits = llval >> 31; + /* will give -1 for negative, 0 or 1 for positive */ + if (valp && (upperbits == 0 || upperbits == -1 || upperbits == 1)) { + *valp = (unsigned) llval; + return 1; + } + return 0; + } +} + + +void usage(char *fname) { + printf("Usage: %s val1 val2 ...\n", fname); + printf("Values may be given as hex patterns or as floating point numbers\n"); + exit(0); +} + + +int main(int argc, char *argv[]) +{ + int i; + unsigned uf; + if (argc < 2) + usage(argv[0]); + for (i = 1; i < argc; i++) { + char *sval = argv[i]; + if (get_num_val(sval, &uf)) { + show_float(uf); + } else { + printf("Invalid 32-bit number: '%s'\n", sval); + usage(argv[0]); + } + } + return 0; +} + + diff --git a/labs/datalab/datalab-handout/ishow.c b/labs/datalab/datalab-handout/ishow.c new file mode 100644 index 0000000..ffb1df7 --- /dev/null +++ b/labs/datalab/datalab-handout/ishow.c @@ -0,0 +1,75 @@ +/* Display value of fixed point numbers */ +#include <stdlib.h> +#include <stdio.h> + +/* Extract hex/decimal/or float value from string */ +static int get_num_val(char *sval, unsigned *valp) { + char *endp; + /* See if it's an integer or floating point */ + int ishex = 0; + int isfloat = 0; + int i; + for (i = 0; sval[i]; i++) { + switch (sval[i]) { + case 'x': + case 'X': + ishex = 1; + break; + case 'e': + case 'E': + if (!ishex) + isfloat = 1; + break; + case '.': + isfloat = 1; + break; + default: + break; + } + } + if (isfloat) { + return 0; /* Not supposed to have a float here */ + } else { + long long int llval = strtoll(sval, &endp, 0); + long long int upperbits = llval >> 31; + /* will give -1 for negative, 0 or 1 for positive */ + if (valp && (upperbits == 0 || upperbits == -1 || upperbits == 1)) { + *valp = (unsigned) llval; + return 1; + } + return 0; + } +} + +void show_int(unsigned uf) +{ + printf("Hex = 0x%.8x,\tSigned = %d,\tUnsigned = %u\n", + uf, (int) uf, uf); +} + + +void usage(char *fname) { + printf("Usage: %s val1 val2 ...\n", fname); + printf("Values may be given in hex or decimal\n"); + exit(0); +} + +int main(int argc, char *argv[]) +{ + int i; + unsigned uf; + if (argc < 2) + usage(argv[0]); + for (i = 1; i < argc; i++) { + char *sval = argv[i]; + if (get_num_val(sval, &uf)) { + show_int(uf); + } else { + printf("Cannot convert '%s' to 32-bit number\n", sval); + } + } + return 0; +} + + + diff --git a/labs/datalab/datalab-handout/tests.c b/labs/datalab/datalab-handout/tests.c new file mode 100644 index 0000000..38eb9c6 --- /dev/null +++ b/labs/datalab/datalab-handout/tests.c @@ -0,0 +1,118 @@ +/* Testing Code */ + +#include <limits.h> +#include <math.h> + +/* Routines used by floation point test code */ + +/* Convert from bit level representation to floating point number */ +float u2f(unsigned u) { + union { + unsigned u; + float f; + } a; + a.u = u; + return a.f; +} + +/* Convert from floating point number to bit-level representation */ +unsigned f2u(float f) { + union { + unsigned u; + float f; + } a; + a.f = f; + return a.u; +} + +//1 +int test_bitXor(int x, int y) +{ + return x^y; +} +int test_tmin(void) { + return 0x80000000; +} +//2 +int test_isTmax(int x) { + return x == 0x7FFFFFFF; +} +int test_allOddBits(int x) { + int i; + for (i = 1; i < 32; i+=2) + if ((x & (1<<i)) == 0) + return 0; + return 1; +} + + + + + + + +int test_negate(int x) { + return -x; +} +//3 + + +int test_isAsciiDigit(int x) { + return (0x30 <= x) && (x <= 0x39); +} +int test_conditional(int x, int y, int z) +{ + return x?y:z; +} +int test_isLessOrEqual(int x, int y) +{ + return x <= y; +} +//4 +int test_logicalNeg(int x) +{ + return !x; +} +int test_howManyBits(int x) { + unsigned int a, cnt; + x = x<0 ? -x-1 : x; + a = (unsigned int)x; + for (cnt=0; a; a>>=1, cnt++) + ; + + return (int)(cnt + 1); +} +//float +unsigned test_floatScale2(unsigned uf) { + float f = u2f(uf); + float tf = 2*f; + if (isnan(f)) + return uf; + else + return f2u(tf); +} +int test_floatFloat2Int(unsigned uf) { + float f = u2f(uf); + int x = (int) f; + return x; +} +unsigned test_floatPower2(int x) { + float result = 1.0; + float p2 = 2.0; + int recip = (x < 0); + /* treat tmin specially */ + if ((unsigned)x == 0x80000000) { + return 0; + } + if (recip) { + x = -x; + p2 = 0.5; + } + while (x > 0) { + if (x & 0x1) + result = result * p2; + p2 = p2 * p2; + x >>= 1; + } + return f2u(result); +} diff --git a/labs/malloclab/malloclab-handout.tar b/labs/malloclab/malloclab-handout.tar Binary files differnew file mode 100644 index 0000000..a6b6392 --- /dev/null +++ b/labs/malloclab/malloclab-handout.tar diff --git a/labs/malloclab/malloclab.pdf b/labs/malloclab/malloclab.pdf Binary files differnew file mode 100644 index 0000000..03d2187 --- /dev/null +++ b/labs/malloclab/malloclab.pdf diff --git a/labs/proxylab/proxylab-handout.tar b/labs/proxylab/proxylab-handout.tar Binary files differnew file mode 100644 index 0000000..61d6093 --- /dev/null +++ b/labs/proxylab/proxylab-handout.tar diff --git a/labs/proxylab/proxylab.pdf b/labs/proxylab/proxylab.pdf Binary files differnew file mode 100644 index 0000000..4620899 --- /dev/null +++ b/labs/proxylab/proxylab.pdf diff --git a/labs/shlab/shlab-handout.tar b/labs/shlab/shlab-handout.tar Binary files differnew file mode 100644 index 0000000..853cd30 --- /dev/null +++ b/labs/shlab/shlab-handout.tar diff --git a/labs/shlab/shlab.pdf b/labs/shlab/shlab.pdf Binary files differnew file mode 100644 index 0000000..cb2b4b9 --- /dev/null +++ b/labs/shlab/shlab.pdf |