The Trunk: Kernel-nice.1229.mcz

Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-nice.1229.mcz

==================== Summary ====================

Name: Kernel-nice.1229
Author: nice
Time: 9 May 2019, 9:10:10.673329 am
UUID: 4836a3a9-d962-4d8f-9180-5285b8e7c96a
Ancestors: Kernel-cmm.1228

Fix (0 bitShift: 100) is not normalized
    (0 bitShift: 100) class = LargePositiveInteger.

Why is it not normalized?
First, primitiveBitShift (17) fails because shift is longer than SmallInteger bit length (maybe it should not?), then bitShiftMagnitude: (primDigitBitShiftMagnitude:) does not normalize a left shift result, assuming that primitive 17 already did the trivial work if result were a SmallInteger.

Why is normalization important?
because non normalized Integers do not behave like SmallInteger and can cause all sort of undefined behavior (I had an infinite loop because of that)

How to fix?
just handle the case in primitive fallback code

While at it:
Do not use bitShiftMagnitude: when we do not need to (case of left shift are equivalent to bitShift:), because playing with not normalized results may lead to undefined behavior.

=============== Diff against Kernel-cmm.1228 ===============

Item was changed:
  ----- Method: LargePositiveInteger>>digitMul22: (in category 'private') -----
  digitMul22: anInteger
  "Multiply after decomposing each operand in two parts, using Karatsuba algorithm.
  Karatsuba perform only 3 multiplications, leading to a cost O(n^3 log2)
  asymptotically better than super O(n^2) for large number of digits n.
  See https://en.wikipedia.org/wiki/Karatsuba_algorithm"
 
  | half xLow xHigh yLow yHigh low mid high |
  "Divide each integer in two halves"
  half := (anInteger digitLength + 1 bitShift: -1)  bitClear: 2r11.
  xLow := self lowestNDigits: half.
  xHigh := self butLowestNDigits: half.
  yLow := anInteger lowestNDigits: half.
  yHigh := anInteger butLowestNDigits: half.
 
  "Karatsuba trick: perform with 3 multiplications instead of 4"
  low := xLow multiplyByInteger: yLow.
  high := xHigh multiplyByInteger: yHigh.
  mid := high + low + (xHigh - xLow multiplyByInteger: yLow - yHigh).
 
  "Sum the parts of decomposition"
  ^(high isZero
  ifTrue: [low]
+ ifFalse: [(high bitShift: 16*half)
- ifFalse: [(high bitShiftMagnitude: 16*half)
  inplaceAddNonOverlapping: low digitShiftBy: 0])
+ + (mid bitShift: 8*half)!
- + (mid bitShiftMagnitude: 8*half)!

Item was changed:
  ----- Method: LargePositiveInteger>>squaredByHalf (in category 'private') -----
  squaredByHalf
  "Use a divide and conquer algorithm to perform the multiplication.
  Split in two parts like Karatsuba, but economize 2 additions by using asymetrical product."
 
  | half xHigh xLow low high mid |
 
  "Divide digits in two halves"
  half := self digitLength + 1 // 2 bitClear: 2r11.
  xLow := self lowestNDigits: half.
  xHigh := self butLowestNDigits: half.
 
  "eventually use karatsuba"
  low := xLow squared.
  high := xHigh squared.
  mid := xLow multiplyByInteger: xHigh.
 
  "Sum the parts of decomposition"
+ ^(high bitShift: 16*half)
- ^(high bitShiftMagnitude: 16*half)
  inplaceAddNonOverlapping: low digitShiftBy: 0;
+ + (mid bitShift: 8*half+1)
- + (mid bitShiftMagnitude: 8*half+1)
 
  "
  | a |
  a := 440 factorial-1.
  a digitLength.
  self assert: a * a - a squaredKaratsuba = 0.
  [Smalltalk garbageCollect.
  [2000 timesRepeat: [a squaredKaratsuba]] timeToRun] value /
  [Smalltalk garbageCollect.
  [2000 timesRepeat: [a * a]] timeToRun] value asFloat
  "!

Item was changed:
  ----- Method: SmallInteger>>bitShift: (in category 'bit manipulation') -----
  bitShift: arg
  "Primitive. Answer an Integer whose value is the receiver's value shifted
  left by the number of bits indicated by the argument. Negative arguments
  shift right. The receiver is interpreted as having 2's-complement representation.
  Essential.  See Object documentation whatIsAPrimitive."
 
  <primitive: 17>
+ self = 0 ifTrue: [^self].
+ self > 0 ifTrue: [^ super bitShift: arg].
- self >= 0 ifTrue: [^ super bitShift: arg].
  ^ arg >= 0
  ifTrue: [(self negated bitShift: arg) negated]
  ifFalse: [(self bitInvert bitShift: arg) bitInvert]!

On 09/05/19 8:14 AM, [hidden email] wrote:
>     ^ arg >= 0
>     ifTrue: [(self negated bitShift: arg) negated]
>     ifFalse: [(self bitInvert bitShift: arg) bitInvert]!
should this also be split into

        arg = 0 ifTrue: [^self].
        arg > 0
                ...

Regards .. Subbu