/* UPE library * (c)2000 Stepan Roh * see license.txt for copying */ #include "upe.h" #include #include #include #include #include #include #include #define MAX(a,b) (((a)>(b))?(a):(b)) #define MIN(a,b) (((a)<(b))?(a):(b)) /* UPE_LOW_MEM_FN is called on low memory - if #defined */ #ifdef UPE_LOW_MEM_FN #define return_low_mem(x) UPE_LOW_MEM_FN () #else #define return_low_mem(x) return (x) #endif /* shift value to the right for given bits_in_byte and return shifted value * temp_val is temprary variable to store result in */ #define UPE_SHIFT_LOW_BITS(val,temp_val,bits_in_byte)\ (((temp_val) = (val) & ((1 << (bits_in_byte)) - 1)), ((val) >>= (bits_in_byte)), (temp_val)) /* shift value to the left, add given bits and return result */ #define UPE_UNSHIFT_LOW_BITS(val,what,bits_in_byte)\ ((val) = ((val) << (bits_in_byte)) | (what)) /* number of valid bits in last upe_byte of variable-sized integer */ #define UPE_LAST_BITS(bits,bits_in_byte)\ ((bits_in_byte) - ((UPE_NUM_OF_BYTES((bits),(bits_in_byte)) * (bits_in_byte)) - (bits))) /* mask low bits - leave only those */ #define UPE_MASK_LOW_BITS(val,bits)\ ((bits) ? ((val) & ((1 << (upe_u64_t)(bits)) - 1)) : 0) /* mask high bits - leave only those */ #define UPE_MASK_HIGH_BITS(val,bits,bits_in_byte)\ ((val) & ~((1 << (upe_u64_t)((bits_in_byte) - (bits))) - 1)) #ifdef UPE_BYTE_SIZE_AS_VAR /* number of bits in one byte - max. 32 bits */ upe_u32_t upe_byte_size = 8; #endif /* byte order mapping for loading/storing from/to memory * upe_byte_order[length_in_bytes][byte_number] returns new byte_number * length_in_bytes starts at 0 for 1 byte length values * byte_number starts at 0 for first byte */ upe_u32_t **upe_byte_order = NULL; /* byte order mapping length */ int upe_byte_order_len = 0; /* add new byte order : * byte length is determined by call strlen(order) * byte_numbers are taken from characters 123456789 * (which means first, second, ... byte) * any form is permitted even weird onnes ("1111" etc.) * returns 0 on success, -2 on low memory, -1 on input error (chars others than 1-9) */ int upe_add_byte_order (char *order) { int len, i; assert (order); len = strlen (order); if (len < 1) return -1; if (len > upe_byte_order_len) { if (!(upe_byte_order = realloc (upe_byte_order, sizeof (upe_u32_t *) * len))) return_low_mem (-2); memset (upe_byte_order + upe_byte_order_len, 0, sizeof (upe_u32_t *) * (len - upe_byte_order_len)); upe_byte_order_len = len; } if (!upe_byte_order[len - 1]) { if (!(upe_byte_order[len - 1] = malloc (sizeof (upe_u32_t) * len))) return_low_mem (-2); } for (i = 0; i < len; i++) { if ((order[i] < '1') || (order[i] > '9')) return -1; upe_byte_order[len - 1][i] = order[i] - '0' - 1; } return 0; } /* initialise variable-size integer with given size in bits * returns NULL on error, otherwise num */ upe_number_t *upe_initnum (upe_u32_t bits, int sign, upe_sign_type sign_type) { upe_number_t *num; if (!(num = malloc (sizeof (upe_number_t)))) return_low_mem (NULL); num->size = bits; num->sign = sign; num->sign_type = sign_type; if (!(num->val_ptr = (upe_u32_t *)malloc (sizeof (upe_u32_t) * UPE_NUM_OF_BYTES (bits, upe_byte_size)))) return_low_mem (NULL); return num; } /* deinitialise previously initialised variable-size integer * if UPE_FREE_NULL is defined, destroying NULL nums is permitted without error */ void upe_donenum (upe_number_t *num) { #ifndef UPE_FREE_NULL assert (num); assert (num->val_ptr); #endif #ifdef UPE_FREE_NULL if (num) { if (num->val_ptr) #endif free (num->val_ptr); free (num); #ifdef UPE_FREE_NULL } #endif } /* store one upe_byte (upe_u32_t) in variable-size integer according to upe_byte_order * byte = byte value * bytes = size in bytes * byte_num = byte number */ static upe_number_t *upe_setnum_byte (upe_number_t *num, upe_u32_t byte, upe_u32_t bytes, upe_u32_t byte_num) { assert (num); assert (num->val_ptr); assert (bytes >= 0); #ifndef UPE_NOT_BYTE_ORDER if ((bytes < upe_byte_order_len) && upe_byte_order[bytes - 1]) byte_num = upe_byte_order[bytes - 1][byte_num]; #endif num->val_ptr[byte_num] = byte; return num; } /* get one upe_byte (upe_u32_t) from variable-size integer according to upe_byte_order * bytes = size in bytes * byte_num = byte number */ static upe_u32_t upe_getnum_byte (upe_number_t *num, upe_u32_t bytes, upe_u32_t byte_num) { assert (num); assert (num->val_ptr); assert (bytes >= 0); #ifdef UPE_NOT_BYTE_ORDER return num->val_ptr[byte_num]; #else if ((bytes < upe_byte_order_len) && upe_byte_order[bytes - 1]) return num->val_ptr[upe_byte_order[bytes - 1][byte_num]]; else return num->val_ptr[byte_num]; #endif } /* convert integer to variable-size integer */ upe_number_t *upe_setnum (upe_number_t *num, int inum) { int i, b, nb, temp; assert (num); assert (num->val_ptr); upe_zeronum (num); i = sizeof (inum) * CHARBITS; i = MIN (i, num->size); /* truncate if bigger */ b = 0; nb = UPE_NUM_OF_BYTES (i, upe_byte_size); while (i > 0) { num->val_ptr[b] = UPE_SHIFT_LOW_BITS (inum, temp, MIN (upe_byte_size, i)); i -= upe_byte_size; b++; } return num; } /* convert variable-size integer to integer * - may give strange results if variable-size integer is bigger than * machine integer */ int upe_getnum (upe_number_t *num) { int i, b, nb, inum; assert (num); assert (num->val_ptr); i = sizeof (inum) * CHARBITS; i = MIN (i, num->size); inum = 0; nb = UPE_NUM_OF_BYTES (i, upe_byte_size); b = nb - 1; while (i > 0) { UPE_UNSHIFT_LOW_BITS (inum, num->val_ptr[b], upe_byte_size); i -= upe_byte_size; b--; } return inum; } /* convert integer string representation to variable-size integer, * which is initialised to number of bits necessary for input * whitespaces are ignored * possible formats : binary 0b[0-1]+ * hexadecimal 0x[0-9a-fA-F]+ * octal 0[0-7]+ * decimal [0-9]+ * stops parsing on first error or too big number and returns NULL (but with possible modifications to num) * warning: only binary input is supported for whole range, * others are emulated by strtol() */ upe_number_t *upe_strtonum (upe_number_t *num, char *str) { char *s; int b, nb, base, i; upe_u32_t v; assert (str); assert (num); upe_zeronum (num); if (*str) { while (isspace (*str)) str++; if (*str == '0') { str++; if (*str == 'b') { base = 2; str++; } else if (*str == 'x') { base = 16; str++; } else base = 8; } else base = 10; if (base == 2) { s = strchr (str, 0) - 1; while (isspace (*s)) s--; if (s - str + 1 > num->size) return NULL; nb = UPE_NUM_OF_BYTES (num->size, upe_byte_size); b = 0; for (s = strchr (str, 0) - 1; s >= str; s -= upe_byte_size) { v = 0; for (i = 0; i < MIN (upe_byte_size, s - str + 1); i++) { if (s[-i] == '1') v |= 1 << i; } upe_setnum_byte (num, v, nb, b); b++; } } else { upe_setnum (num, strtol (str, NULL, base)); /* !!! temporary hack !!! */ } } return num; } /* assigns zero to variable-size integer */ upe_number_t *upe_zeronum (upe_number_t *num) { assert (num); assert (num->val_ptr); memset (num->val_ptr, 0, sizeof (upe_u32_t) * UPE_NUM_OF_BYTES (num->size, upe_byte_size)); return num; } /* dest += src * if result doesn't fit into dest and overflow is not NULL, then overflow is set to 1 (otherwise set to 0) * returns dest */ upe_number_t *upe_addnum (upe_number_t *dest, upe_number_t *src, int *overflow) { int ds, dd, i; upe_u32_t c; upe_u64_t r; assert (dest); assert (dest->val_ptr); assert (src); assert (src->val_ptr); ds = UPE_NUM_OF_BYTES (src->size, upe_byte_size); dd = UPE_NUM_OF_BYTES (dest->size, upe_byte_size); c = 0; for (i = 0; i < MIN(ds, dd); i++) { r = (upe_u64_t)src->val_ptr[i] + (upe_u64_t)dest->val_ptr[i] + c; if ((dd <= ds) && (i == dd - 1)) { c = r >> UPE_LAST_BITS(dest->size, upe_byte_size); r = UPE_MASK_LOW_BITS(r, UPE_LAST_BITS(dest->size, upe_byte_size)); } else { c = r >> upe_byte_size; r = UPE_MASK_LOW_BITS(r, upe_byte_size); } dest->val_ptr[i] = r; } if (overflow) *overflow = c ? 1 : 0; return dest; } /* dest -= src * if result is below 0 and underflow is not NULL, then underflow is set to 1 (otherwise set to 0) * returns dest */ upe_number_t *upe_subnum (upe_number_t *dest, upe_number_t *src, int *underflow) { int ds, dd, i, c; upe_s64_t r; assert (dest); assert (dest->val_ptr); assert (src); assert (src->val_ptr); ds = UPE_NUM_OF_BYTES (src->size, upe_byte_size); dd = UPE_NUM_OF_BYTES (dest->size, upe_byte_size); c = 0; for (i = 0; i < MIN(ds, dd); i++) { r = (upe_u64_t)dest->val_ptr[i] - (upe_u64_t)src->val_ptr[i] - c; c = (r < 0); if (r < 0) { if ((dd <= ds) && (i == dd - 1)) { r = (1 << (upe_u64_t)UPE_LAST_BITS(dest->size, upe_byte_size)) + r; } else { r = (1 << (upe_u64_t)upe_byte_size) + r; } } dest->val_ptr[i] = r; } if (underflow) *underflow = c ? 1 : 0; return dest; } /* dest = src * if dest has more bits, then they are filled with zeros * if dest has less bits, then only lesser bits of src are copied * returns dest */ upe_number_t *upe_copynum (upe_number_t *dest, upe_number_t *src) { int ds, dd, i; assert (dest); assert (dest->val_ptr); assert (src); assert (src->val_ptr); ds = UPE_NUM_OF_BYTES (src->size, upe_byte_size); dd = UPE_NUM_OF_BYTES (dest->size, upe_byte_size); for (i = 0; i < MIN(ds, dd); i++) { if ((dd < ds) && (i == dd - 1)) { dest->val_ptr[i] = UPE_MASK_LOW_BITS(src->val_ptr[i], UPE_LAST_BITS(dest->size, upe_byte_size)); } else { dest->val_ptr[i] = src->val_ptr[i]; } } return dest; } /* duplicates variable-sized integer (like init & copy) */ upe_number_t *upe_dupnum (upe_number_t *src) { upe_number_t *dest; assert (src); assert (src->val_ptr); if (!(dest = upe_initnum (src->size, src->sign, src->sign_type))) return_low_mem (NULL); return upe_copynum (dest, src); } /* duplicates bit-range of variable-sized integer * bits are numbered from 0 */ upe_number_t *upe_dupnum_range (upe_number_t *src, upe_u32_t bit_from, upe_u32_t bit_to) { upe_number_t *dest; int byte_from, byte_to, i, dest_bits, byte_num, src_bits; assert (src); assert (src->val_ptr); if (!(dest = upe_initnum (bit_to - bit_from + 1, src->sign, src->sign_type))) return_low_mem (NULL); upe_zeronum (dest); if ((bit_from < 0) || (bit_from > bit_to)) return dest; byte_from = UPE_NUM_OF_BYTES (MIN (bit_from + 1, src->size), upe_byte_size) - 1; byte_to = UPE_NUM_OF_BYTES (MIN (bit_to + 1, src->size), upe_byte_size) - 1; if (byte_from == byte_to) { dest->val_ptr[0] = src->val_ptr[byte_from] >> (bit_from - (byte_from * upe_byte_size)); dest->val_ptr[0] = UPE_MASK_LOW_BITS (dest->val_ptr[0], bit_to - bit_from + 1); } else { /* description of algorithm : * src [01234][01234][01234] * we want this part |--| |---| || * it's splitted | | || | || * and shifted | || | || * dest [ ][23401][23401] */ byte_num = 0; dest_bits = 0; src_bits = bit_from - (byte_from * upe_byte_size); for (i = byte_from; i <= byte_to; i++) { if (i != byte_from) { if (dest_bits) { dest->val_ptr[byte_num] |= UPE_MASK_LOW_BITS (src->val_ptr[i], upe_byte_size - dest_bits) << dest_bits; byte_num++; dest_bits = 0; src_bits = bit_from - (byte_from * upe_byte_size); } else if (i == byte_to) { dest->val_ptr[byte_num] |= UPE_MASK_LOW_BITS (src->val_ptr[i], bit_to - (upe_byte_size * byte_to) + 1) << dest_bits; src_bits = 0; } } if (i != byte_to) { dest->val_ptr[byte_num] |= UPE_MASK_HIGH_BITS (src->val_ptr[i], upe_byte_size - src_bits, upe_byte_size) >> src_bits; dest_bits += upe_byte_size - src_bits; if (dest_bits >= upe_byte_size) { dest_bits = 0; byte_num++; } src_bits = 0; } else if ((i == byte_to) && src_bits) { dest->val_ptr[byte_num] |= UPE_MASK_LOW_BITS (src->val_ptr[i], bit_to - (upe_byte_size * byte_to) + 1) >> src_bits; } } } return dest; } /* dest <<= num * returns dest */ upe_number_t *upe_shlnum (upe_number_t *dest, upe_u32_t num) { int dd, i, j, shift_bytes, shift_bits; upe_u64_t b; upe_number_t *src; assert (dest); assert (dest->val_ptr); dd = UPE_NUM_OF_BYTES (dest->size, upe_byte_size); if (num <= 0) return dest; if (num <= 64) { b = 0; for (i = dd - 1; i >= 0; i--) { b = ((upe_u64_t)dest->val_ptr[i]) << num; if (i == dd - 1) { dest->val_ptr[i] = UPE_MASK_LOW_BITS (b, UPE_LAST_BITS (dest->size, upe_byte_size)); } else { dest->val_ptr[i] = UPE_MASK_LOW_BITS (b, upe_byte_size); for (j = i + 1; j < dd; j++) { b >>= upe_byte_size; dest->val_ptr[j] |= UPE_MASK_LOW_BITS (b, (j == dd - 1) ? UPE_LAST_BITS (dest->size, upe_byte_size) : upe_byte_size); } } } } else { if (!(src = upe_dupnum (dest))) return_low_mem (NULL); upe_zeronum (dest); shift_bytes = UPE_NUM_OF_BYTES (num + 1, upe_byte_size) - 1; shift_bits = num - (shift_bytes * upe_byte_size); for (i = 0; i < dd; i++) { j = i + shift_bytes; if (j < dd) { dest->val_ptr[j] |= UPE_MASK_LOW_BITS (src->val_ptr[i], upe_byte_size - shift_bits) << shift_bits; } j++; if (j < dd) { dest->val_ptr[j] |= UPE_MASK_HIGH_BITS (src->val_ptr[i], shift_bits, upe_byte_size) >> (upe_byte_size - shift_bits); } } dest->val_ptr[dd - 1] = UPE_MASK_LOW_BITS (dest->val_ptr[dd - 1], UPE_LAST_BITS (dest->size, upe_byte_size)); upe_donenum (src); } return dest; } /* dest >>= num * returns dest */ upe_number_t *upe_shrnum (upe_number_t *dest, upe_u32_t num) { int dd, i, j, shift_bytes, shift_bits; upe_number_t *src; assert (dest); assert (dest->val_ptr); dd = UPE_NUM_OF_BYTES (dest->size, upe_byte_size); if (num <= 0) return dest; if (!(src = upe_dupnum (dest))) return_low_mem (NULL); upe_zeronum (dest); shift_bytes = UPE_NUM_OF_BYTES (num + 1, upe_byte_size) - 1; shift_bits = num - (shift_bytes * upe_byte_size); for (i = 0; i < dd; i++) { j = i - shift_bytes; if (j >= 0) { dest->val_ptr[j] |= UPE_MASK_HIGH_BITS (src->val_ptr[i], upe_byte_size - shift_bits, upe_byte_size) >> shift_bits; } j--; if (j >= 0) { dest->val_ptr[j] |= UPE_MASK_LOW_BITS (src->val_ptr[i], shift_bits) << (upe_byte_size - shift_bits); } } dest->val_ptr[dd - 1] = UPE_MASK_LOW_BITS (dest->val_ptr[dd - 1], UPE_LAST_BITS (dest->size, upe_byte_size)); upe_donenum (src); return dest; } /* num++ * if result doesn't fit into dest and overflow is not NULL, then overflow is set to 1 (otherwise set to 0) * returns dest */ upe_number_t *upe_incnum (upe_number_t *num, int *overflow) { int dd, i, c; assert (num); assert (num->val_ptr); dd = UPE_NUM_OF_BYTES (num->size, upe_byte_size); c = 1; for (i = 0; i < dd; i++) { num->val_ptr[i] = UPE_MASK_LOW_BITS (num->val_ptr[i] + 1, (i == dd - 1) ? UPE_LAST_BITS (num->size, upe_byte_size) : upe_byte_size); if (num->val_ptr[i]) { c = 0; break; } } if (overflow) *overflow = c; return num; } /* num-- * if result is below 0 and underflow is not NULL, then underflow is set to 1 (otherwise set to 0) * returns dest */ upe_number_t *upe_decnum (upe_number_t *num, int *underflow) { int dd, i, c, b; assert (num); assert (num->val_ptr); dd = UPE_NUM_OF_BYTES (num->size, upe_byte_size); c = 1; b = 0; for (i = 0; i < dd; i++) { if (num->val_ptr[i]) { c = 0; b = 1; } num->val_ptr[i] = UPE_MASK_LOW_BITS (num->val_ptr[i] - 1, (i == dd - 1) ? UPE_LAST_BITS (num->size, upe_byte_size) : upe_byte_size); if (b) break; } if (underflow) *underflow = c; return num; } /* returns (num == 0) */ int upe_iszero (upe_number_t *num) { int d, i; assert (num); assert (num->val_ptr); d = UPE_NUM_OF_BYTES (num->size, upe_byte_size); for (i = 0; i < d; i++) { if (num->val_ptr[i] != 0) return 0; } return 1; } /* num = !num * returns num */ upe_number_t *upe_negnum (upe_number_t *num) { int d, i; assert (num); assert (num->val_ptr); d = UPE_NUM_OF_BYTES (num->size, upe_byte_size); for (i = 0; i < d; i++) { if (num->val_ptr[i] != 0) return upe_zeronum (num); } num->val_ptr[0] = 1; return num; } /* dest &&= src * returns dest */ upe_number_t *upe_andnum (upe_number_t *dest, upe_number_t *src) { int dd, ds, i; assert (dest); assert (dest->val_ptr); assert (src); assert (src->val_ptr); dd = UPE_NUM_OF_BYTES (dest->size, upe_byte_size); ds = UPE_NUM_OF_BYTES (src->size, upe_byte_size); for (i = 0; i < dd; i++) { if (dest->val_ptr[i] != 0) { for (i = 0; i < ds; i++) { if (src->val_ptr[i] != 0) { upe_zeronum (dest); dest->val_ptr[0] = 1; return dest; } } return upe_zeronum (dest); } } return dest; } /* dest ||= src * returns dest */ upe_number_t *upe_ornum (upe_number_t *dest, upe_number_t *src) { int dd, ds, i; assert (dest); assert (dest->val_ptr); assert (src); assert (src->val_ptr); dd = UPE_NUM_OF_BYTES (dest->size, upe_byte_size); ds = UPE_NUM_OF_BYTES (src->size, upe_byte_size); for (i = 0; i < dd; i++) { if (dest->val_ptr[i] != 0) return dest; } for (i = 0; i < ds; i++) { if (src->val_ptr[i] != 0) { dest->val_ptr[0] = 1; return dest; } } return dest; } /* num = ~num * returns num */ upe_number_t *upe_bitnegnum (upe_number_t *num) { int d, i; assert (num); assert (num->val_ptr); d = UPE_NUM_OF_BYTES (num->size, upe_byte_size); for (i = 0; i < d; i++) { num->val_ptr[i] = ~num->val_ptr[i]; if (i == d - 1) num->val_ptr[i] = UPE_MASK_LOW_BITS (num->val_ptr[i], upe_byte_size); else num->val_ptr[i] = UPE_MASK_LOW_BITS (num->val_ptr[i], UPE_LAST_BITS (num->size, upe_byte_size)); } return num; } /* dest &= src * returns dest */ upe_number_t *upe_bitandnum (upe_number_t *dest, upe_number_t *src) { int dd, ds, i; assert (dest); assert (dest->val_ptr); assert (src); assert (src->val_ptr); dd = UPE_NUM_OF_BYTES (dest->size, upe_byte_size); ds = UPE_NUM_OF_BYTES (src->size, upe_byte_size); for (i = 0; i < MIN (dd, ds); i++) { dest->val_ptr[i] &= src->val_ptr[i]; } for (i = MIN (dd, ds); i < dd; i++) { dest->val_ptr[i] = 0; } return dest; } /* dest |= src * returns dest */ upe_number_t *upe_bitornum (upe_number_t *dest, upe_number_t *src) { int dd, ds, i; assert (dest); assert (dest->val_ptr); assert (src); assert (src->val_ptr); dd = UPE_NUM_OF_BYTES (dest->size, upe_byte_size); ds = UPE_NUM_OF_BYTES (src->size, upe_byte_size); for (i = 0; i < MIN (dd, ds); i++) { dest->val_ptr[i] |= src->val_ptr[i]; } return dest; } /* dest ^= src * returns dest */ upe_number_t *upe_bitxornum (upe_number_t *dest, upe_number_t *src) { int dd, ds, i; assert (dest); assert (dest->val_ptr); assert (src); assert (src->val_ptr); dd = UPE_NUM_OF_BYTES (dest->size, upe_byte_size); ds = UPE_NUM_OF_BYTES (src->size, upe_byte_size); for (i = 0; i < MIN (dd, ds); i++) { dest->val_ptr[i] ^= src->val_ptr[i]; } for (i = MIN (dd, ds); i < dd; i++) { dest->val_ptr[i] ^= 0; } return dest; } /* returns (n1 < n2) */ int upe_ltnum (upe_number_t *n1, upe_number_t *n2) { int d1, d2, i; assert (n1); assert (n1->val_ptr); assert (n2); assert (n2->val_ptr); d1 = UPE_NUM_OF_BYTES (n1->size, upe_byte_size); d2 = UPE_NUM_OF_BYTES (n2->size, upe_byte_size); for (i = MAX(d1, d2) - 1; i >= 0; i--) { upe_u32_t v1, v2; if (i >= d1) v1 = 0; else v1 = n1->val_ptr[i]; if (i >= d2) v2 = 0; else v2 = n2->val_ptr[i]; if (v1 < v2) return 1; else if (v1 > v2) return 0; } return 0; } /* returns (n1 <= n2) */ int upe_lenum (upe_number_t *n1, upe_number_t *n2) { int d1, d2, i; assert (n1); assert (n1->val_ptr); assert (n2); assert (n2->val_ptr); d1 = UPE_NUM_OF_BYTES (n1->size, upe_byte_size); d2 = UPE_NUM_OF_BYTES (n2->size, upe_byte_size); for (i = MAX(d1, d2) - 1; i >= 0; i--) { upe_u32_t v1, v2; if (i >= d1) v1 = 0; else v1 = n1->val_ptr[i]; if (i >= d2) v2 = 0; else v2 = n2->val_ptr[i]; if (v1 < v2) return 1; else if (v1 > v2) return 0; } return 1; } /* returns (n1 == n2) */ int upe_eqnum (upe_number_t *n1, upe_number_t *n2) { int d1, d2, i; assert (n1); assert (n1->val_ptr); assert (n2); assert (n2->val_ptr); d1 = UPE_NUM_OF_BYTES (n1->size, upe_byte_size); d2 = UPE_NUM_OF_BYTES (n2->size, upe_byte_size); for (i = MAX(d1, d2) - 1; i >= 0; i--) { upe_u32_t v1, v2; if (i >= d1) v1 = 0; else v1 = n1->val_ptr[i]; if (i >= d2) v2 = 0; else v2 = n2->val_ptr[i]; if (v1 != v2) return 0; } return 1; } /* memory range structure */ typedef struct upe_mem_range_t { upe_number_t *from, *to; /* range */ int read_access, write_access; /* >0 - permitted, =0 - violation, <0 - fake */ upe_read_mem_fn read_fn; /* users read function */ upe_write_mem_fn write_fn; /* users write function */ unsigned char *adr; /* address to real memory */ size_t len; /* size in real memory bytes */ struct upe_mem_range_t *next; /* next range in chain */ } upe_mem_range_t; /* upe memory structure */ struct upe_mem_t { int num; /* number of pools */ upe_mem_range_t **pools; /* pools - pointers to first memory ranges */ }; /* create new memory with given number of memory pools * returns NULL on error */ upe_mem_t *upe_create_mem (int pools) { upe_mem_t *mem; if (pools <= 0) return NULL; if (!(mem = malloc (sizeof (upe_mem_t)))) return_low_mem (NULL); mem->num = pools; if (!(mem->pools = malloc (sizeof (upe_mem_range_t *) * pools))) return_low_mem (NULL); memset (mem->pools, 0, sizeof (upe_mem_range_t *) * pools); return mem; } /* destroy memory and everything associated with it (pools, ranges) */ void upe_destroy_mem (upe_mem_t *mem) { int i; upe_mem_range_t *r, *n; assert (mem); for (i = 0; i < mem->num; i++) { r = mem->pools[i]; while (r) { n = r->next; upe_donenum (r->from); upe_donenum (r->to); free (r); r = n; } } free (mem->pools); } /* map real memory to emulated one (in given mem and pool) * read_access - read accessibility (>0 - permitted, =0 - violation, <0 - fake) * read_fn - is called in upe_read_mem, but with val already initialised and read access checked * write_access - write accessibility (>0 - permitted, =0 - violation, <0 - fake) * write_fn - is called in upe_write_mem, but with write access checked */ int upe_map_mem (upe_mem_t *mem, int pool, upe_number_t *from, upe_number_t *to, unsigned char *adr, int read_access, upe_read_mem_fn read_fn, int write_access, upe_write_mem_fn write_fn) { upe_mem_range_t *m; assert (mem); if ((pool < 0) || (pool >= mem->num)) return -1; if (!(m = malloc (sizeof (upe_mem_range_t)))) return_low_mem (-1); if (!(m->from = upe_dupnum (from))) return_low_mem (-1); if (!(m->to = upe_dupnum (to))) return_low_mem (-1); m->len = upe_getnum (upe_subnum (m->to, m->from, NULL)) + 1; upe_copynum (m->to, to); m->adr = adr; m->read_access = read_access; m->write_access = write_access; m->read_fn = read_fn; m->write_fn = write_fn; m->next = mem->pools[pool]; mem->pools[pool] = m; return 0; } /* read given number of bits from memory * adr - real memory address * b_size - number of bits to read * upe_adr - address in b_size chunks into adr */ static upe_u32_t upe_get_mem (unsigned char *adr, size_t upe_adr, int b_size) { upe_u64_t bytes_around = 0; int i; size_t real_adr_bytes, real_adr_bits; upe_u32_t r; assert (b_size > 0); real_adr_bytes = UPE_NUM_OF_BYTES ((upe_adr * b_size) + 1, CHARBITS) - 1; real_adr_bits = (upe_adr * b_size) - (real_adr_bytes * CHARBITS); for (i = 0; i < UPE_NUM_OF_BYTES (b_size + real_adr_bits, CHARBITS); i++) { bytes_around <<= CHARBITS; bytes_around |= adr[real_adr_bytes + i]; } bytes_around >>= real_adr_bits; r = UPE_MASK_LOW_BITS (bytes_around, b_size); return r; } /* write given number of bits to memory * adr - real memory address * b_size - number of bits to read * upe_adr - address in b_size chunks into adr * v - value to write (b_size lowest bits) */ static void upe_set_mem (unsigned char *adr, size_t upe_adr, int b_size, upe_u32_t v) { int i; size_t real_adr_bytes, real_adr_bits, last_byte, last_bits; assert (b_size > 0); real_adr_bytes = UPE_NUM_OF_BYTES ((upe_adr * b_size) + 1, CHARBITS) - 1; real_adr_bits = (upe_adr * b_size) - (real_adr_bytes * CHARBITS); last_byte = UPE_NUM_OF_BYTES (b_size + real_adr_bits, CHARBITS); adr[real_adr_bytes] = UPE_MASK_LOW_BITS (adr[real_adr_bytes], real_adr_bits) | (UPE_MASK_LOW_BITS (v, CHARBITS - real_adr_bits) << real_adr_bits); v >>= CHARBITS - real_adr_bits; for (i = 1; i < last_byte - 1; i++) { adr[real_adr_bytes + i] = UPE_MASK_LOW_BITS (v, CHARBITS); v >>= CHARBITS; } if (last_byte > 2) { last_bits = (b_size + real_adr_bits) % CHARBITS; if (!last_bits) adr[real_adr_bytes + last_byte - 1] = v; else adr[real_adr_bytes + last_byte - 1] = UPE_MASK_HIGH_BITS (adr[real_adr_bytes + last_byte - 1], CHARBITS - last_bits, CHARBITS) | v; } } /* read from memory (mem and pool) bytes upe_bytes starting at adr into val * val will be initialised to (bytes * upe_byte_size) bits * reading is performed using upe_byte_order * returns 0 on success, -1 on memory violation, -2 on out of real mem */ int upe_read_mem (upe_mem_t *mem, int pool, upe_number_t *adr, upe_u32_t bytes, upe_number_t **val) { upe_mem_range_t *r; upe_number_t *n; size_t upe_adr, i; assert (mem); if (!(*val = upe_initnum (bytes * upe_byte_size, 0, UPE_NO_SIGN))) return_low_mem (-2); upe_zeronum (*val); if ((pool < 0) || (pool >= mem->num)) return -1; r = mem->pools[pool]; while (r) { if (upe_genum (adr, r->from) && upe_lenum (adr, r->to)) { if (!r->read_access) return -1; /* memv */ if (r->read_access < 0) return 0; /* fake */ if (bytes > r->len) return -1; if (r->read_fn) return r->read_fn (mem, pool, adr, bytes, val); if (!(n = upe_dupnum (adr))) return_low_mem (-2); upe_adr = upe_getnum (upe_subnum (n, r->from, NULL)); upe_donenum (n); for (i = 0; i < bytes; i++) { upe_u32_t v; if (upe_adr >= r->len) return -1; v = upe_get_mem (r->adr, upe_adr, upe_byte_size); upe_setnum_byte (*val, v, bytes, i); upe_adr++; } return 0; } r = r->next; } return -1; } /* write val to memory (mem and pool) on adr * write is performed using upe_byte_order for number of bytes which val has (rounded up) * returns 0 on success, -1 on memory violation, -2 on out of real mem */ int upe_write_mem (upe_mem_t *mem, int pool, upe_number_t *adr, upe_number_t *val) { upe_mem_range_t *r; upe_number_t *n; size_t upe_adr, i; upe_u32_t bytes; assert (mem); assert (val); assert (val->val_ptr); bytes = UPE_NUM_OF_BYTES (val->size, upe_byte_size); if ((pool < 0) || (pool >= mem->num)) return -1; r = mem->pools[pool]; while (r) { if (upe_genum (adr, r->from) && upe_lenum (adr, r->to)) { if (!r->write_access) return -1; /* memv */ if (r->write_access < 0) return 0; /* fake */ if (bytes > r->len) return -1; if (r->write_fn) return r->write_fn (mem, pool, adr, val); if (!(n = upe_dupnum (adr))) return_low_mem (-2); upe_adr = upe_getnum (upe_subnum (n, r->from, NULL)); upe_donenum (n); for (i = 0; i < bytes; i++) { upe_u32_t v; v = upe_getnum_byte (val, bytes, i); if (upe_adr >= r->len) return -1; upe_set_mem (r->adr, upe_adr, upe_byte_size, v); upe_adr++; } return 0; } r = r->next; } return -1; }