From 51169f5f9ab178a4ddfe9dac461405a71c9c0f94 Mon Sep 17 00:00:00 2001 From: Mike Vink Date: Wed, 22 May 2024 08:49:29 +0200 Subject: organise --- 2/3_int_arith/212.c | 36 ++ 2/3_int_arith/225.c | 20 + 2/3_int_arith/227.c | 20 + 2/3_int_arith/230.c | 25 ++ 2/3_int_arith/236.c | 19 + 2/3_int_arith/242.c | 14 + 2/3_int_arith/243.c | 22 ++ 2/3_int_arith/check | Bin 0 -> 15688 bytes 2/3_int_arith/check-211.c | 27 ++ 2/3_int_arith/show-bytes.c | 33 ++ 2/3_int_arith/xdr.c | 28 ++ 2/4_floating_point/51.ora | Bin 0 -> 3142 bytes 2/4_floating_point/special_values.c | 39 ++ 2/homework/2.59.c | 186 +++++++++ 2/homework/2.66.c | 134 +++++++ 2/homework/2.73.c | 113 ++++++ 2/homework/2.77.c | 108 ++++++ 2/homework/2.80.c | 157 ++++++++ 2/homework/2.87.c | 6 + 2/homework/2.88.c | 54 +++ 2/homework/2.90.c | 112 ++++++ 2/homework/2.92.c | 402 ++++++++++++++++++++ 2/homework/2.96.c | 8 + 2/homework/285.ora | Bin 0 -> 740819 bytes 2/homework/bytes_structure_2.71.c | 67 ++++ 2/homework/implement_calloc.c | 28 ++ 2/homework/logical_and_or.c | 8 + 2/homework/shift_by_w_minus_k.c | 37 ++ 3/3_data_formats/main.c | 16 + 3/3_data_formats/mstore/mstore.c | 6 + 3/3_data_formats/mstore/mstore.s | 21 ++ 3/4_register_and_addresses/main.c | 27 ++ 3/5_arith_and_logic/movq_size.s | 16 + 3/5_arith_and_logic/remdiv.c | 12 + 3/5_arith_and_logic/remdiv.s | 38 ++ 3/5_arith_and_logic/reverse_assemble.c | 23 ++ 3/5_arith_and_logic/sarl.c | 11 + 3/5_arith_and_logic/store_uprod.c | 11 + 3/5_arith_and_logic/store_uprod.s | 27 ++ 3/5_arith_and_logic/xorq_size.c | 5 + 3/5_arith_and_logic/xorq_size.s | 16 + 3/6_control/20_op_bias.c | 10 + 3/6_control/21_test_cmov.c | 20 + 3/6_control/22_loop.c | 51 +++ 3/6_control/23_reverse_engineer_loop.c | 28 ++ 3/6_control/24_while_loop.c | 24 ++ 3/6_control/absdiff_goto.c | 39 ++ 3/6_control/comp.c | 36 ++ 3/6_control/cond.c | 6 + 3/6_control/missing.c | 13 + code/intro/hello.c | 7 - flake.lock | 173 +++++++++ flake.nix | 40 ++ labs/archlab/archlab-handout.tar | Bin 0 -> 1392640 bytes labs/archlab/archlab.pdf | Bin 0 -> 166655 bytes labs/attacklab/attacklab.pdf | Bin 0 -> 189138 bytes labs/attacklab/target1.tar | Bin 0 -> 174080 bytes labs/bomblab/bomb.tar | Bin 0 -> 40960 bytes labs/bomblab/bomblab.pdf | Bin 0 -> 23093 bytes labs/cachelab/cachelab-handout.tar | Bin 0 -> 4116480 bytes labs/cachelab/cachelab.pdf | Bin 0 -> 47072 bytes labs/datalab/datalab-handout/Driverhdrs.pm | 12 + labs/datalab/datalab-handout/Driverlib.pm | 138 +++++++ labs/datalab/datalab-handout/Makefile | 24 ++ labs/datalab/datalab-handout/README | 140 +++++++ labs/datalab/datalab-handout/bits.c | 360 ++++++++++++++++++ labs/datalab/datalab-handout/bits.h | 31 ++ labs/datalab/datalab-handout/btest.c | 583 +++++++++++++++++++++++++++++ labs/datalab/datalab-handout/btest.h | 32 ++ labs/datalab/datalab-handout/decl.c | 57 +++ labs/datalab/datalab-handout/driver.pl | 439 ++++++++++++++++++++++ labs/datalab/datalab-handout/fshow.c | 151 ++++++++ labs/datalab/datalab-handout/ishow.c | 75 ++++ labs/datalab/datalab-handout/tests.c | 118 ++++++ labs/malloclab/malloclab-handout.tar | Bin 0 -> 92160 bytes labs/malloclab/malloclab.pdf | Bin 0 -> 39851 bytes labs/proxylab/proxylab-handout.tar | Bin 0 -> 133120 bytes labs/proxylab/proxylab.pdf | Bin 0 -> 100614 bytes labs/shlab/shlab-handout.tar | Bin 0 -> 81920 bytes labs/shlab/shlab.pdf | Bin 0 -> 35668 bytes 80 files changed, 4532 insertions(+), 7 deletions(-) create mode 100644 2/3_int_arith/212.c create mode 100644 2/3_int_arith/225.c create mode 100644 2/3_int_arith/227.c create mode 100644 2/3_int_arith/230.c create mode 100644 2/3_int_arith/236.c create mode 100644 2/3_int_arith/242.c create mode 100644 2/3_int_arith/243.c create mode 100755 2/3_int_arith/check create mode 100644 2/3_int_arith/check-211.c create mode 100644 2/3_int_arith/show-bytes.c create mode 100644 2/3_int_arith/xdr.c create mode 100644 2/4_floating_point/51.ora create mode 100644 2/4_floating_point/special_values.c create mode 100644 2/homework/2.59.c create mode 100644 2/homework/2.66.c create mode 100644 2/homework/2.73.c create mode 100644 2/homework/2.77.c create mode 100644 2/homework/2.80.c create mode 100644 2/homework/2.87.c create mode 100644 2/homework/2.88.c create mode 100644 2/homework/2.90.c create mode 100644 2/homework/2.92.c create mode 100644 2/homework/2.96.c create mode 100644 2/homework/285.ora create mode 100644 2/homework/bytes_structure_2.71.c create mode 100644 2/homework/implement_calloc.c create mode 100644 2/homework/logical_and_or.c create mode 100644 2/homework/shift_by_w_minus_k.c create mode 100644 3/3_data_formats/main.c create mode 100644 3/3_data_formats/mstore/mstore.c create mode 100644 3/3_data_formats/mstore/mstore.s create mode 100644 3/4_register_and_addresses/main.c create mode 100644 3/5_arith_and_logic/movq_size.s create mode 100644 3/5_arith_and_logic/remdiv.c create mode 100644 3/5_arith_and_logic/remdiv.s create mode 100644 3/5_arith_and_logic/reverse_assemble.c create mode 100644 3/5_arith_and_logic/sarl.c create mode 100644 3/5_arith_and_logic/store_uprod.c create mode 100644 3/5_arith_and_logic/store_uprod.s create mode 100644 3/5_arith_and_logic/xorq_size.c create mode 100644 3/5_arith_and_logic/xorq_size.s create mode 100644 3/6_control/20_op_bias.c create mode 100644 3/6_control/21_test_cmov.c create mode 100644 3/6_control/22_loop.c create mode 100644 3/6_control/23_reverse_engineer_loop.c create mode 100644 3/6_control/24_while_loop.c create mode 100644 3/6_control/absdiff_goto.c create mode 100644 3/6_control/comp.c create mode 100644 3/6_control/cond.c create mode 100644 3/6_control/missing.c delete mode 100644 code/intro/hello.c create mode 100644 flake.lock create mode 100644 flake.nix create mode 100644 labs/archlab/archlab-handout.tar create mode 100644 labs/archlab/archlab.pdf create mode 100644 labs/attacklab/attacklab.pdf create mode 100644 labs/attacklab/target1.tar create mode 100644 labs/bomblab/bomb.tar create mode 100644 labs/bomblab/bomblab.pdf create mode 100644 labs/cachelab/cachelab-handout.tar create mode 100644 labs/cachelab/cachelab.pdf create mode 100644 labs/datalab/datalab-handout/Driverhdrs.pm create mode 100644 labs/datalab/datalab-handout/Driverlib.pm create mode 100644 labs/datalab/datalab-handout/Makefile create mode 100644 labs/datalab/datalab-handout/README create mode 100644 labs/datalab/datalab-handout/bits.c create mode 100644 labs/datalab/datalab-handout/bits.h create mode 100644 labs/datalab/datalab-handout/btest.c create mode 100644 labs/datalab/datalab-handout/btest.h create mode 100644 labs/datalab/datalab-handout/decl.c create mode 100755 labs/datalab/datalab-handout/driver.pl create mode 100644 labs/datalab/datalab-handout/fshow.c create mode 100644 labs/datalab/datalab-handout/ishow.c create mode 100644 labs/datalab/datalab-handout/tests.c create mode 100644 labs/malloclab/malloclab-handout.tar create mode 100644 labs/malloclab/malloclab.pdf create mode 100644 labs/proxylab/proxylab-handout.tar create mode 100644 labs/proxylab/proxylab.pdf create mode 100644 labs/shlab/shlab-handout.tar create mode 100644 labs/shlab/shlab.pdf 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 + +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 +#include + +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 +#include + +// 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 +#include + +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 +#include +#include + +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 + +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 + +int main() { + int x = 3; + printf("%d", x<<1); +} diff --git a/2/3_int_arith/check b/2/3_int_arith/check new file mode 100755 index 0000000..f50a240 Binary files /dev/null and b/2/3_int_arith/check differ 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 + +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 + +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 +#include +#include +#include +#include + +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 new file mode 100644 index 0000000..f39bc3f Binary files /dev/null and b/2/4_floating_point/51.ora differ 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 + +#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 +#include + +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 + +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<>(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 +#include +#include +#include + +/* + 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 +#include +#include + +/* 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 +*/ +int divide_power2(int x, int k) { + /* Get ones mask if msb is set */ + int msb = (x>>31); + int bias = (1<> k; +} + +int mul3div4(int x) { + /* Multiply by 3 */ + x += (x<<1); + + int k = 2; + int msb = (x>>31); + int bias = (1<> 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; + /* 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 +#include +#include +#include + +unsigned bit_pattern_A(int k) { + return (~0)<> 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< 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 -> always true + -x -y -> alwyas true + -x +y -> x-y is also true, since the sign changes + +x -y -> x-y is also false, since the sign changes + */ + printf("A: %d\n", (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 + +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 +#include +#include + +/* + 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 +#include +#include +#include +#include +#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< +#include +#include +#include +#include +#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<>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<>(23 - exp)); + if (sign) { + result = ~result + 1; + } + return result; + } + if (exp < 31) { + int result = (1<>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< 23) { + /* Outside of float32 precision */ + + /* Special case, Is remainder greater than half precision removed from highest power? */ + if ((1<>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 +#include + +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 +#include +#include + +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 + +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 +#include + +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 + +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 + +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 + +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 + +/* + * 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 + +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 + +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 + +// 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 +#include +#include +// 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 + +// 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 + +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 - -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 new file mode 100644 index 0000000..979db4e Binary files /dev/null and b/labs/archlab/archlab-handout.tar differ diff --git a/labs/archlab/archlab.pdf b/labs/archlab/archlab.pdf new file mode 100644 index 0000000..2f1169e Binary files /dev/null and b/labs/archlab/archlab.pdf differ diff --git a/labs/attacklab/attacklab.pdf b/labs/attacklab/attacklab.pdf new file mode 100644 index 0000000..89f63ea Binary files /dev/null and b/labs/attacklab/attacklab.pdf differ diff --git a/labs/attacklab/target1.tar b/labs/attacklab/target1.tar new file mode 100644 index 0000000..b72a423 Binary files /dev/null and b/labs/attacklab/target1.tar differ diff --git a/labs/bomblab/bomb.tar b/labs/bomblab/bomb.tar new file mode 100644 index 0000000..3d38d79 Binary files /dev/null and b/labs/bomblab/bomb.tar differ diff --git a/labs/bomblab/bomblab.pdf b/labs/bomblab/bomblab.pdf new file mode 100644 index 0000000..e5594f5 Binary files /dev/null and b/labs/bomblab/bomblab.pdf differ diff --git a/labs/cachelab/cachelab-handout.tar b/labs/cachelab/cachelab-handout.tar new file mode 100644 index 0000000..93c988e Binary files /dev/null and b/labs/cachelab/cachelab-handout.tar differ diff --git a/labs/cachelab/cachelab.pdf b/labs/cachelab/cachelab.pdf new file mode 100644 index 0000000..b2af686 Binary files /dev/null and b/labs/cachelab/cachelab.pdf differ 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 = ; + 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 = ) { + if ($line =~ /^\r\n/) { + last; + } + } + + # Read and return the response from the result server + $line = ; + 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 ] [-f [-1|-2|-3 ]*] [-T