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 ++++ 28 files changed, 1703 insertions(+) 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 (limited to '2') 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); + +} -- cgit v1.2.3