[squeak-dev] The Trunk: Kernel-nice.771.mcz

commits at source.squeak.org commits at source.squeak.org
Tue Jun 18 21:29:10 UTC 2013


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!



More information about the Squeak-dev mailing list