The Trunk: Kernel-nice.771.mcz

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

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

Name: Kernel-nice.771
Author: nice
Time: 18 June 2013, 11:28:04.495 pm
UUID: e6da6bb0-0aa4-4400-b96c-c53dc343584a
Ancestors: Kernel-fbs.770

Start deprecating usage of \\\
A long comment in \\\ tells the reasons for deprecating

=============== Diff against Kernel-fbs.770 ===============

Item was changed:
  ----- Method: Integer>>\\\ (in category 'arithmetic') -----
  \\\ anInteger
+       "A modulo method former used in DSA."
+
+       "Notes: this method used to be a faster than \\ for LargeIntegers, but this advantage is fainting:
+       - it always was slower for SmallInteger because of the indirection below
+       - a new LargeInteger primitive makes \\ faster up to 64 bits operands
+       - even above 64 bits, its advantage has become marginal thanks to revised \\ primitive fallback code
+       Moreover, \\\ behaviour is questionable for these reasons:
+       - for a negative receiver xor argument, it behaves like rem: for LargeInteger and \\ for SmallInteger
+       - it may answer a not normalized LargeInteger (with leading null digits) which breaks some invariants
+       For example, check (SmallInteger maxVal + 1 \\\ 8) isZero.
+       So beware if you ever think using this method."
-       "a modulo method for use in DSA. Be careful if you try to use this elsewhere"

        ^self \\ anInteger!

Item was changed:
  ----- Method: Integer>>reciprocalModulo: (in category 'arithmetic') -----
  reciprocalModulo: n
        "Answer an integer x such that (self * x) \\ n = 1, x > 0, x < n.
        Raise an error if there is no such integer.
        The algorithm is a non extended euclidean modular inversion called NINV.
        It is described in this article:
                'Using an RSA Accelerator for Modular Inversion'
        by Martin Seysen. See http://www.iacr.org/archive/ches2005/017.pdf"

        | u v f fPlusN b result result2 |
        ((self <= 0) or: [n <= 0]) ifTrue: [self error: 'self and n must be greater than zero'].
        self >= n ifTrue: [self error: 'self must be < n'].

        b := n highBit + 1.
        f := 1 bitShift: b.
        v := (self bitShift: b) + 1.
        u := n bitShift: b.
        fPlusN := f + n.
        [v >= fPlusN] whileTrue:
+               [v := u \\ (u := v)].
-               [v := u \\\ (u := v)].
        result := v - f.
        (result2 := result + n) > 0
                ifFalse: [self error: 'no inverse'].
        ^result positive
                ifTrue: [result]
                ifFalse: [result2]!

Item was changed:
  ----- Method: Integer>>slidingLeftRightRaisedTo:modulo: (in category 'private') -----
  slidingLeftRightRaisedTo: n modulo: m
        "Private - compute (self raisedTo: n) \\ m,
        Note: this method has to be fast because it is generally used with large integers in cryptography.
        It thus operate on exponent bits from left to right by packets with a sliding window rather than bit by bit (see below)."

        | pow j k w index oddPowersOfSelf square |

        "Precompute powers of self for odd bit patterns xxxx1 up to length w + 1.
        The width w is chosen with respect to the total bit length of n,
        such that each bit pattern will on average be encoutered P times in the whole bit sequence of n.
        This costs (2 raisedTo: w) multiplications, but more will be saved later (see below)."
        k := n highBit.
        w := (k highBit - 1 >> 1 min: 16) max: 1.
        oddPowersOfSelf := Array new: 1 << w.
        oddPowersOfSelf at: 1 put: (pow := self).
+       square := self * self \\ m.
+       2 to: oddPowersOfSelf size do: [:i | pow := oddPowersOfSelf at: i put: pow * square \\ m].
-       square := self * self \\\ m.
-       2 to: oddPowersOfSelf size do: [:i | pow := oddPowersOfSelf at: i put: pow * square \\\ m].

        "Now exponentiate by searching precomputed bit patterns with a sliding window"
        pow := 1.
        [k > 0]
                whileTrue:
+                       [pow := pow * pow \\ m.
-                       [pow := pow * pow \\\ m.
                        "Skip bits set to zero (the sliding window)"
                        (n bitAt: k) = 0
                                ifFalse:
                                        ["Find longest odd bit pattern up to window length (w + 1)"
                                        j := k - w max: 1.
                                        [j < k and: [(n bitAt: j) = 0]] whileTrue: [j := j + 1].
                                        "We found an odd bit pattern of length k-j+1;
                                        perform the square powers for each bit
                                        (same cost as bitwise algorithm);
                                        compute the index of this bit pattern in the precomputed powers."
                                        index := 0.
                                        [k > j] whileTrue:
+                                               [pow := pow * pow \\ m.
-                                               [pow := pow * pow \\\ m.
                                                index := index << 1 + (n bitAt: k).
                                                k := k - 1].
                                        "Perform a single multiplication for the whole bit pattern.
                                        This saves up to (k-j) multiplications versus a naive algorithm operating bit by bit"
+                                       pow := pow * (oddPowersOfSelf at: index + 1) \\ m].
-                                       pow := pow * (oddPowersOfSelf at: index + 1) \\\ m].
                        k := k - 1].
+       ^pow!
-       ^pow normalize!

Item was changed:
  ----- Method: LargePositiveInteger>>\\\ (in category 'arithmetic') -----
  \\\ anInteger
+       "A modulo method former used in DSA.
+       This method is not much faster than \\ and rem: and it breaks some invariants (see super).
+       Usage is now deprecated and should be reserved to backward compatibility."
-       "a faster modulo method for use in DSA. Be careful if you try to use this elsewhere"

        ^(self digitDiv: anInteger neg: false) second!