| blob | 8fb7222c08a8c0adddac90e4962a178dd1de4a6b |
1 ;;;; simple cases for generic arithmetic
3 ;;;; This software is part of the SBCL system. See the README file for
4 ;;;; more information.
5 ;;;;
6 ;;;; This software is derived from the CMU CL system, which was
7 ;;;; written at Carnegie Mellon University and released into the
8 ;;;; public domain. The software is in the public domain and is
9 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
10 ;;;; files for more information.
22 fixnum-tag-mask))
30 fixnum-tag-mask))
31 )
33 #+sb-xc-host
36 \f
37 ;;;; addition, subtraction, and multiplication
56 ,@body
60 DO-STATIC-FUN
61 ;; Same as: (inst enter (* n-word-bytes 1))
75 ;; Unbox the overflowed result, recovering the correct sign from
76 ;; the carry flag, then re-box as a bignum.
86 OKAY)
93 ;; Unbox the overflowed result, recovering the correct sign from
94 ;; the carry flag, then re-box as a bignum.
104 OKAY)
125 SINGLE-WORD-BIGNUM
131 OKAY
133 DONE))
134 \f
135 ;;;; negation
157 FIXNUM
167 OKAY)
168 \f
169 ;;;; comparison
190 DO-STATIC-FUN
197 -3
198 ocfp-save-offset)))
199 rbp-tn)
203 -3
204 ocfp-save-offset))))
207 ;; HACK: We depend on NIL having the lowest address of all
208 ;; static symbols (including T)
232 ;; At least one fixnum
236 DO-STATIC-FUN
243 -3
244 ocfp-save-offset)))
245 rbp-tn)
249 -3
250 ocfp-save-offset))))
270 ;; Both fixnums
274 DO-STATIC-FUN
281 -3
282 ocfp-save-offset)))
283 rbp-tn)
287 -3
288 ocfp-save-offset))))
295 #+sb-assembling
302 ;; See the comments below for how the algorithm works. The tricks
303 ;; used can be found for example in AMD's software optimization
304 ;; guide or at "http://www.hackersdelight.org/HDcode/pop.cc" in the
305 ;; function "pop1", for 32-bit words. The extension to 64 bits is
306 ;; straightforward.
307 ;; Calculate 2-bit sums. Note that the value of a two-digit binary
308 ;; number is the sum of the right digit and twice the left digit.
309 ;; Thus we can calculate the sum of the two digits by shifting the
310 ;; left digit to the right position and doing a two-bit subtraction.
311 ;; This subtraction will never create a borrow and thus can be made
312 ;; on all 32 2-digit numbers at once.
318 ;; Calculate 4-bit sums by straightforward shift, mask and add.
319 ;; Note that we shift the source operand of the MOV and not its
320 ;; destination so that the SHR and the MOV can execute in the same
321 ;; clock cycle.
328 ;; Calculate 8-bit sums. Since each sum is at most 8, which fits
329 ;; into 4 bits, we can apply the mask after the addition, saving one
330 ;; instruction.
336 ;; Add all 8 bytes at once by multiplying with #256r11111111.
337 ;; We need to calculate only the lower 8 bytes of the product.
338 ;; Of these the most significant byte contains the final result.
339 ;; Note that there can be no overflow from one byte to the next
340 ;; as the sum is at most 64 which needs only 7 bits.
350 #!-sb-dynamic-core
354 #!+sb-dynamic-core
360 ;; To perform logcount on small integers, we test whether to use the
361 ;; builtin opcode, or an assembly routine. I benchmarked this against
362 ;; an approach that always used the assembly routine via "call [addr]"
363 ;; where the contents of the address reflected one implementation
364 ;; or the other, chosen at startup - and this is faster.
365 #-sb-assembling
376 ;; input/output of assembly routine
379 ;; Assembly routine clobbers RAX and RCX but only needs to save RAX,
380 ;; as this vop clobbers RCX in the call. If changed to "CALL [ADDR]"
381 ;; be sure to update the subroutine to push and pop RCX.
386 ;; POPCNT = ECX bit 23 = bit 7 of byte index 2
387 ;; this use of 'rcx' is as the temporary register for performing
388 ;; a reference to foreign data with dynamic core. It has to be
389 ;; a register that conflicts with 'arg' lest we clobber it.
392 ;; Intel's implementation of POPCNT on some models treats it as
393 ;; a 2-operand ALU op in the manner of ADD,SUB,etc which means that
394 ;; it falsely appears to need data from the destination register.
395 ;; The workaround is to clear the destination.
396 ;; See http://stackoverflow.com/questions/25078285
398 ;; We only break the spurious dep. chain if result isn't the same
399 ;; register as arg. (If they're location=, don't trash the arg!)
403 slow
407 done))))
411 ;;; EQL for integers that are either fixnum or bignum
413 ;; The restriction on use of this assembly routine can't be expressed a
414 ;; constraints on vop args: it may be called when at *least* one arg
415 ;; is known to be an integer; the other can be anything.
416 ;
417 ;; Logic: we succeed quickly in the EQ case when possible.
418 ;; Otherwise, check if both are OTHER-POINTER objects, failing if not.
419 ;; Given that at least one is an integer, and both are OTHER-POINTERs,
420 ;; then if their widetags match, both are BIGNUMs to be compared word-for-word.
421 ;;
422 ;; If you call this with two other-pointer objects with
423 ;; the same widetag, but not bignum-widetag, the behavior is undefined.
424 ;;
427 ;; :safe would imply signaling an error
428 ;; if the args are not integer, which this doesn't.
439 ;; check that both have other-pointer-lowtag
447 ;; Compare the entire header word, ensuring that if at least one
448 ;; argument is a bignum, then both are.
453 ;; can you have 0 payload words? probably not, but let's be safe here.
455 loop
460 ;; These next 3 instructions are the equivalent of "LOOPNZ LOOP"
461 ;; but had significantly better performance for me, consistent with claims
462 ;; of most optimization guides saying that LOOP was deliberately pessimized
463 ;; because of its use in timing-related code in the win32 kernel.
467 ;; If the Z flag is set, the integers were EQL
468 done)