1 # Arithmetic, Level 1 2 # operates on Digit Sequences (DS) and Unsigned Digit Sequences (UDS). 3 4 5 # From LISPBIBL.D this file imports: 6 # intDsize number of bits in a digit 7 # uintD, sintD integer types for a digit 8 # log2_intDsize log2(intDsize) 9 # HAVE_DD flag signalling whether an integer type for double-digit is 10 # available 11 # intDDsize number of bits in a double-digit 12 # uintDD,sintDD integer types for a double-digit 13 14 #if !((32%intDsize)==0) 15 #error intDsize should be a divisor of 32! 16 #endif 17 18 19 # Determine the sign of a digit: 20 # sign_of_sintD(value) 21 # > value: a digit 22 # < sintD result: 0 if value>=0, -1 if value<0. 23 global sint32 sign_of_sintD (sintD value); 24 #if (intDsize==16) 25 #define sign_of_sintD(x) (sintD)(sign_of_sint16(x)) 26 #endif 27 #if (intDsize==32) 28 #define sign_of_sintD(x) (sintD)(sign_of_sint32(x)) 29 #endif 30 31 # Determine the high digit of a double-digit: 32 # highD(value) 33 #if HAVE_DD 34 #if (!(intDsize==16)) 35 #define highD(x) ((uintD)((uintDD)(x)>>intDsize)) 36 #else 37 #define highD high16 38 #endif 39 #endif 40 41 # Determine the low digit of a double-digit: 42 # lowD(value) 43 #if HAVE_DD 44 #define lowD(x) ((uintD)(uintDD)(x)) 45 #endif 46 47 # Determine a double-digit from its high digit and its low digit parts: 48 # highlowDD(uintD high, uintD low) 49 #if HAVE_DD 50 #if (!(intDsize==16)) 51 #define highlowDD(x,y) (((uintDD)(uintD)(x)<<intDsize)|(uintDD)(uintD)(y)) 52 #else 53 #define highlowDD highlow32 54 #endif 55 #endif 56 57 # Determine a double-digit from its high digit and its low digit given as 0: 58 # highlowDD_0(uintD high) 59 #if HAVE_DD 60 #if (!(intDsize==16)) 61 #define highlowDD_0(x) ((uintDD)(uintD)(x)<<intDsize) 62 #else 63 #define highlowDD_0 highlow32_0 64 #endif 65 #endif 66 67 # Multiply two digits: 68 # (uintDD)hilo = muluD(uintD arg1, uintD arg2) 69 # bzw. 70 # muluD(uintD arg1, uintD arg2, uintD hi =, uintD lo =); 71 #if HAVE_DD 72 #if (intDsize==16) 73 #define muluD mulu16 74 #endif 75 #if (intDsize==32) && defined(HAVE_LONG_LONG_INT) 76 #define muluD(arg1,arg2) ((uintDD)(uintD)(arg1)*(uintDD)(uintD)(arg2)) 77 #endif 78 #else 79 #if (intDsize==32) 80 #define muluD mulu32 81 #endif 82 #endif 83 84 # Multiply two digits, when the result is a single digit. 85 # (uintD)lo = muluD_unchecked(uintD arg1, uintD arg2) 86 # The caller guarantees that arg1*arg2 < 2^intDsize. 87 #if (intDsize==16) 88 #define muluD_unchecked(arg1,arg2) ((uintD)((uintD)(arg1)*(uintD)(arg2))) 89 #endif 90 #if (intDsize==32) 91 #define muluD_unchecked(arg1,arg2) mulu32_unchecked(arg1,arg2) 92 #endif 93 94 # Divide by a digit: 95 # divuD(uintDD x, uintD y, uintD q =, uintD r =); 96 # or 97 # divuD(uintD xhi, uintD xlo, uintD y, uintD q =, uintD r =); 98 # divides x/y and returns q = floor(x/y) and r = (x mod y). x = q*y+r. 99 # The caller guarantees that 0 <= x < 2^intDsize*y. 100 #if HAVE_DD 101 #if (intDsize==16) 102 #define divuD divu_3216_1616 103 #endif 104 #if (intDsize==32) && defined(HAVE_LONG_LONG_INT) 105 #define divuD(x,y,q_assignment,r_assignment) \ 106 { var uint64 __x = (x); \ 107 var uint32 __y = (y); \ 108 var uint32 __q = floor(__x,(uint64)__y); \ 109 q_assignment __q; r_assignment (uint32)__x - __q * __y; \ 110 } 111 #endif 112 #else 113 #if (intDsize==32) 114 #define divuD divu_6432_3232 115 #endif 116 #endif 117 118 # Divide by a digit: 119 # floorD(uintD x, uintD y) 120 # divides x/y and returns q = floor(x/y). 121 # The caller guarantees that y > 0. 122 #if (intDsize==16) 123 #define floorD(arg1,arg2) (floor((uintD)(arg1),(uintD)(arg2))) 124 #endif 125 #if (intDsize==32) 126 #define floorD divu_3232_3232_ 127 #endif 128 129 # Digit Sequence (DS) - only used internally - 130 # A consecutive piece of memory, with n digits (n being an uintC), 131 # located between two pointers MSDptr and LSDptr. 132 # MSDptr LSDptr 133 # | MSD ............. LSD | 134 # [abbreviation: MSDptr/n/LSDptr ] 135 # Memory range: MSDptr[0..n-1]. 136 # LSDptr is = &MSDptr[n]. 137 # In Big-Endian convention, the most significant digit is located at the lowest 138 # address, namely at MSDptr. LSDptr = MSDptr + n points to the memory beyond 139 # the DS. 140 # If n = 0, the represented number is 0. 141 # If n > 0, the most significant bit (namely bit (intDsize-1) of *MSDptr) is 142 # the sign bit. After repeating it infinitely often, one obtains an 143 # "infinite bit sequence". 144 # 145 # Normalisierte Digit Sequence (NDS) 146 # is a digit sequence for which the MSD is necessary, i.e. cannot be optimized 147 # away. I.e. either n = 0 or (n > 0 and the intDsize+1 most significant bits 148 # are not all the same). 149 # In C: 150 # uintD* MSDptr and uintC len. 151 # MSDptr[0] ... MSDptr[len-1] are the digits. 152 153 # Unsigned Digit Sequence (UDS) - only used internally - 154 # is like DS (MSD at low addresses, LSD at high addresses), except without a 155 # sign. 156 # 157 # Normalized Unsigned Digit Sequence (NUDS): 158 # like UDS, for which the number cannot be represented as an UDS with fewer 159 # digits: either n = 0 (represents the number 0) or if n > 0: *MSDptr >0. 160 # In C: 161 # uintD* MSDptr und uintC len. 162 # MSDptr[0] ... MSDptr[len-1] are the digits. 163 164 # For constructing compile-time constant DS: 165 # D(byte0,byte1,byte2,byte3,) returns the 32 bits of {byte0,byte1,byte2,byte3} 166 # as 32/intDsize digits. 167 #if (intDsize==16) 168 #define D(byte0,byte1,byte2,byte3,dummy) ((byte0<<8)|byte1),((byte2<<8)|byte3), 169 #endif 170 #if (intDsize==32) 171 #define D(byte0,byte1,byte2,byte3,dummy) \ 172 (((uintD)(byte0)<<24)|((uintD)(byte1)<<16)|((uintD)(byte2)<<8)|((uintD)(byte3))), 173 #endif 174 175 typedef struct { uintD* MSDptr; uintC len; uintD* LSDptr; } DS; 176 177 178 # For the innermost loops there are six possible implementations: 179 # LOOP_EXTERN_C All loops as extern C compiled functions. 180 # Portable, but possibly inefficient. 181 # LOOP_STATIC_C All loops as C compiled functions in the same compilation 182 # unit. Optimizing compilers may inline them. 183 # Portable, but possibly inefficient. 184 # LOOP_INLINE_C Loops that don't return a value (or with GNU C: all loops) 185 # as C macros. 186 # Portable, but possibly inefficient. 187 # LOOP_EXTERN_ASM All loops as external assembler functions. 188 # More efficient, but still a function call overhead. 189 # LOOP_DEBUG_ASM All loops as wrappers around the external assembler 190 # functions that verify the results of each function call. 191 # Neither portable nor efficient. 192 # Use for debugging of the external assembler functions. 193 # LOOP_INLINE_ASM Loops that don't return a value (or with GNU C: all loops) 194 # as macroexpanded inline assembler routines. 195 # Very efficient. 196 197 #if defined(ARILEV1_EXTERN) 198 #define LOOP_EXTERN_C 199 #elif (defined(SPARC) || defined(I80386) || defined(MIPS) || defined(ARM)) && !defined(NO_ARI_ASM) 200 # diese Assembler beherrsche ich 201 #if (defined(GNU) && defined(WANT_LOOP_INLINE)) 202 # der GNU-Compiler kann Inline-Assembler 203 #define LOOP_INLINE_ASM 204 #elif defined(DEBUG_ARI_ASM) 205 # Use wrapper definitions. 206 #define LOOP_DEBUG_ASM 207 #else 208 # sonst mit externen Routinen arbeiten 209 #define LOOP_EXTERN_ASM 210 #endif 211 #else 212 # sonst die portable Lösung 213 #if (defined(DECALPHA) && defined(GNU) && (intDsize==32) && defined(HAVE_DD)) 214 # GCC-2.7.2-Bug umgehen 215 #define LOOP_STATIC_C 216 #else 217 #define LOOP_INLINE_C 218 #endif 219 #endif 220 221 222 #ifdef LOOP_EXTERN_C 223 #define maybe_local 224 #define C(symbol) symbol 225 # Die Definitionen samt portablem C-Code: 226 #include "arilev1c.c" 227 #undef C 228 #undef maybe_local 229 #endif 230 231 #ifdef LOOP_STATIC_C 232 #define maybe_local local 233 #define C(symbol) symbol 234 # Die Definitionen samt portablem C-Code: 235 #include "arilev1c.c" 236 #undef C 237 #undef maybe_local 238 #endif 239 240 # Die Inline-Macros 241 #ifdef LOOP_INLINE_ASM 242 # sind momentan nicht implementiert 243 #define LOOP_EXTERN_ASM # stattdessen extern in Assembler 244 #endif 245 246 #if defined(LOOP_EXTERN_ASM) || defined(LOOP_DEBUG_ASM) 247 # Die Assembler-Definitionen: 248 #define INCLUDED_FROM_C 249 #if defined(SPARC) 250 #if defined(SPARC64) 251 #include "ari_asm_sparc64.c" 252 #else 253 #include "ari_asm_sparc.c" 254 #endif 255 #endif 256 #if defined(I80386) 257 #include "ari_asm_i386.c" 258 #endif 259 #if defined(MIPS) 260 #if defined(MIPS64) && defined(WIDE_HARD) 261 #include "ari_asm_mips64.c" 262 #else /* o32 or n32 ABI */ 263 #include "ari_asm_mips.c" 264 #endif 265 #endif 266 #if defined(ARM) 267 #include "ari_asm_arm.c" 268 #endif 269 #undef INCLUDED_FROM_C 270 # Die Extern-Deklarationen: 271 #include "arilev1e.c" 272 #ifdef LOOP_DEBUG_ASM 273 # The portable definitions, under a different name: 274 #define maybe_local local 275 #define C(symbol) portable_##symbol 276 #include "arilev1c.c" 277 #undef C 278 #undef maybe_local 279 # The wrapper definitions: 280 #include "arilev1dbg.c" 281 #endif 282 # Die nicht in Assembler geschriebenen Teile nehmen wir vom portablen C-Code: 283 #define LOOP_INLINE_C 284 #endif 285 286 #ifdef LOOP_INLINE_C 287 # Die Definitionen samt portablem C-Code und 288 # - für den GNU-Compiler - Inline-Deklarationen: 289 #include "arilev1i.c" 290 #endif 291 292