The Trunk: Kernel-ul.1058.mcz

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

The Trunk: Kernel-ul.1058.mcz

commits-2
Levente Uzonyi uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-ul.1058.mcz

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

Name: Kernel-ul.1058
Author: ul
Time: 10 February 2017, 1:16:53.505258 pm
UUID: 62aa1881-7b99-4ba0-bfa5-a2599f1386a9
Ancestors: Kernel-eem.1057

- extracted BitCountPerByteTable from Integer >> bitCount
- added optimized version of #bitCount to SmallInteger

=============== Diff against Kernel-eem.1057 ===============

Item was changed:
  Number subclass: #Integer
  instanceVariableNames: ''
+ classVariableNames: 'BitCountPerByteTable LowBitPerByteTable'
- classVariableNames: 'LowBitPerByteTable'
  poolDictionaries: ''
  category: 'Kernel-Numbers'!
 
  !Integer commentStamp: '<historical>' prior: 0!
  I am a common abstract superclass for all Integer implementations. My implementation subclasses are SmallInteger, LargePositiveInteger, and LargeNegativeInteger.
 
  Integer division consists of:
  / exact division, answers a fraction if result is not a whole integer
  // answers an Integer, rounded towards negative infinity
  \\ is modulo rounded towards negative infinity
  quo: truncated division, rounded towards zero!

Item was changed:
  ----- Method: Integer class>>initialize (in category 'class initialization') -----
  initialize
+ "Integer initialize"
+
+ self
+ initializeLowBitPerByteTable;
+ initializeBitCountPerByteTable!
- "Integer initialize"
- self initializeLowBitPerByteTable!

Item was added:
+ ----- Method: Integer class>>initializeBitCountPerByteTable (in category 'class initialization') -----
+ initializeBitCountPerByteTable
+ "Initialize BitCountPerByteTable which is a ByteArray that contains the number of set bits (1) of the integers between 0 and 255. It's defined as a class variable so that it can be used from the instance side and subclasses too."
+ "Evaluate this expression to form the byte array:
+ ((0 to: 255)
+ collect: [:i |
+ | bitCount n |
+ n := i.
+ bitCount := 0.
+ [n = 0]
+ whileFalse:
+ [bitCount := bitCount + 1.
+ n := n bitAnd: n - 1].
+ bitCount]
+ as: ByteArray)"
+
+ BitCountPerByteTable := #[0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 4 5 5 6 5 6 6 7 5 6 6 7 6 7 7 8]!

Item was changed:
  ----- Method: Integer>>bitCount (in category 'bit manipulation') -----
  bitCount
  "Count the number of bits set to 1 in self"
 
  | bitCount |
  self < 0 ifTrue: [self error: 'Cannot count bits of negative integers'].
  bitCount := 0.
  1 to: self digitLength do: [:i |
+ bitCount := bitCount + (BitCountPerByteTable at: (self digitAt: i) + 1) ].
- bitCount := bitCount + (self digitAt: i) bitCountOfByte].
  ^bitCount!

Item was added:
+ ----- Method: SmallInteger>>bitCount (in category 'bit manipulation') -----
+ bitCount
+ "Count the number of bits set to 1 in self. Overridden for performance"
+
+ | n bitCount |
+ self < 0 ifTrue: [self error: 'Cannot count bits of negative integers'].
+ bitCount := 0.
+ n := self.
+ [ n = 0 ] whileFalse: [
+ bitCount := bitCount + (BitCountPerByteTable at: (n bitAnd: 16rFF) + 1).
+ n := n bitShift: -8 ].
+ ^bitCount!

Item was changed:
  ----- Method: SmallInteger>>bitCountOfByte (in category 'bit manipulation') -----
  bitCountOfByte
  "Count the number of bits set to 1 in a byte."
 
+ ^BitCountPerByteTable at: self + 1!
- ^#[0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 4 5 5 6 5 6 6 7 5 6 6 7 6 7 7 8] at: self + 1
-
- "Evaluate this expression to form above byte array:
- ((0 to: 255)
- collect: [:i |
- | bitCount n |
- n := i.
- bitCount := 0.
- [n = 0]
- whileFalse:
- [bitCount := bitCount + 1.
- n := n bitAnd: n - 1].
- bitCount]
- as: ByteArray)"!