Sunday, December 21, 2014

FTP and WebDAV Plugins for Pharo's FileSystem

Project info

The “FileSystemNetwork” project is a small library which adds WebDAV and FTP support to Pharo’s FileSystem framework. This allows you to use remote WebDAV and FTP locations with the same (FileSystem) API that’s used for disk access.

Project location

The project is located on STHub at http://smalltalkhub.com/#!/~UdoSchneider/FileSystemNetwork

Screenshot

Because the Pharo Tools use FileSystem as their underlying framework even those built-in tools are now able to use remote WebDAV and FTP locations.
Pharo FileList browser on mozilla.org FTP Server

Installation

To install everything (WebDAV, FTP and tests) simply use:

Gofer it
    smalltalkhubUser: 'UdoSchneider' project: 'FileSystemNetwork';
    configuration;
    loadStable.

If you don’t want to load everything the configuration provides (two) three groups:

  • Webdav: (Only WebDav - no tests)
  • FTP: (Only FTP - no tests)
  • Tests: (All tests - loads everything)

E.g. to only load WebDAV support use

Gofer it
    smalltalkhubUser: 'UdoSchneider' project: 'FileSystemNetwork';
    configuration;
    load.
#ConfigurationOfFileSystemNetwork asClass project stableVersion load: 'Webdav'

Use in your own application

Once loaded the FileSystem class provides additional methods (#webdav: and #ftp:) which return a Network filesystem. Both methods take a String or (Zn)Url argument which allows you to specify username, password, host, port and initial working directory (e.g. [scheme]://[username]:[password]@[hostname]:[port][workingdirectory]. Once you obtained the FileSystem you can use the usual FileSystem API (see Files with FileSystem for examples).

NOTE: Please remember to always #close the FileSystem instance. There might be dangling/open instances otherwise!

FTP

"Obtain a FTP FileSystem"
fs := FileSystem ftp: 'ftp://ftp.mozilla.org'.

"Get working directory"
wd := fs workingDirectory .

"Print the following expression!"
(wd / 'pub' / 'firefox') children.

"Open a FileList on the FileSystem"
FileList openOn: wd.

"Remember to close if you are finished!"
fs close.

WebDAV

"Obtain a WebDAV FileSystem"
fs := FileSystem webdav: 'https://udoschneider:PASSWORD@webdav.hidrive.strato.com/users/udoschneider/'.

"Get working directory"
wd := fs workingDirectory.

"Open a FileList on the FileSystem"
FileList openOn: wd.

"Remember to close if you are finished!"
fs close.

Packages

  • FileSystem-Network-Core - package with core/protocol independent functionality
  • FileSystem-Tests-Network-Core - package with core tests
  • FileSystem-Network-FTP - package with FTP functionality
  • FileSystem-Tests-Network-FTP - package with FTP tests
  • FileSystem-Network-Webdav - package with WebDAV functionality
  • FileSystem-Tests-Network-Webdav - package with WebDAV tests

Testing

The package comes with 156 tests in the test packages (most of them inherited from FileSystem tests). All tests are green on the clients/servers I used.

NOTE If you want to verify that a certain server works correctly simply run the tests against this server. Please remember that you need write access for the tests to be successful.

NOTE The server URLs for WebDAV and FTP are not hardcoded in the tests. You will be requested to provide FTP and WebDAV URLs on first run. If you want to reset the cached URLs use FTPFileSystemTest reset.and WebdavFileSystemTest reset..

To Do

Enhanced FTP Server Support

Currently only FTP Servers running on *nix or Windows are supported. Support for NetWare and Rumpus are on the way.

S3 Support

Amazon S3 Support will be integrated soon as most of the functionality is already there due to the WebDAV/HTTP support.

License

The code is under MIT License.

Wednesday, November 26, 2014

PaymentFont for Seaside

Project info

The “PaymentFont for Seaside” project is a small Seaside wrapper for the PaymentFont project. FontPayment is a “sleek SVG webfont containing 74 icons of all main payment operators and methods”.

Project location

The project is located on STHub at http://smalltalkhub.com/#!/~UdoSchneider/PaymentFont/

Screenshot

PaymentFont for Seaside Examples Browser

License

PaymentFont is licensed under SIL OFL 1.1. The CSS files are licensed under the MIT License. The Pharo Smalltalk wrapper code is under MIT License.

Installation

Gofer new
    url: 'http://smalltalkhub.com/mc/UdoSchneider/PaymentFont/main';
    package: 'ConfigurationOfPaymentFont';
    load.
((Smalltalk at: #ConfigurationOfPaymentFont) project stableVersion) load.

Run the Demo locally

Start the web server for Seaside - for instance with Zinc evaluate:

ZnZincServerAdaptor startOn: 8080

Now point your browser to http://127.0.0.1:8080/paymentfont

Use in your own application

Necessary Seaside libraries

To add PaymentFont to your Seaside application you just have to add the appropriate seaside file libraries containing the CSS and fonts to your Seaside application.

Depending on the scenario there is a PFDeploymentLibrary and a PFDevelopmentLibrary that you will find in the package PaymentFont-Core in the category PaymentFont-Core-Libraries.

Have a look at the #register method in the PFExamplesHome class for an example.

Use in your code

If the PaymentFont library is registered with your Seaside application you can use the #pfPaymentIcon selectors in your usual rendering methods (like #renderContentOn:):

renderContentOn: html
    html pfPaymentIcon amazon

Packages

  • PaymentFont-Core - package with the core, contains anything you need in an own app
  • PaymentFont-Tests - package with the SUnit tests
  • PaymentFont-Examples - example package for the demo

Testing

The package comes with 74 tests in the package PaymentFont-Tests. Just use the SUnit TestRunner to run them.

Monday, September 22, 2014

Block Translators - parsing magic

Introduction

I have to admit I do love parsers, BNF grammars and similar stuff. I don’t really understand all this stuff in detail but I love working with it. After being exposed to lex/yacc in a previous life I simply loved using T-Gen, SmallCC from within Smalltalk and now finally settled with PetitParser.

All these parser generators are great if you need to parse a given textual input. In some cases however this is complete overkill. Especially if you need to (dynamically) translate a Smalltalk expression into something “different”.

Translating Smalltalk expressions into “something different” is exactly the usecase for what I call “Block Translators”.

Block Translators

During this Blog Entry I’ll develop a simple Parser/Translator which is able to translate Smalltalk expressions like (customer joinDate year is: Date today year) into an equivalent SQL-like Expression like (YEAR(customers.joinDate) = 2014).
Please note that this Translator will neither be complete in terms of operations nor neatly refactored like you would expect for production code. But it should be able to show the general idea how to create translators which translate a Smalltalk expression into something different.

Smalltalk collection messages as SQL Expression

Smalltalk’s collection messages like #do:, #select: or #detect:ifNone are IMHO one of the biggest features of the class library. Most SQL libraries for Smalltalk also include the feature to express SQL expressions as Smalltalk code. So something like this …

(
    (customer surname is: 'Schneider') or: (customer surname is: 'Mueller')
) and: (
    (customer bonusPoints gt: customer joinDate year) or: (customer joinDate year is: Date today year)
)

… should be translated into something SQL-like like this:

(((customers.surname = 'Schneider') | (customers.surname = 'Mueller')) & ((customers.bonusPoints > YEAR(customers.joinDate)) | (YEAR(customers.joinDate) = 2014)))

One way would be to hook into the Smalltalk compiler and build the SQL-like expression from the AST. Another would be to ignore the Smalltalk side completely and parse Strings via a Parsers into those expressions (again using graphs/ASTs). But in some cases a simpler approach with “Message Recording” objects is more than sufficient.

Blocks as Parsers/Translators

Let’s start with the block from above. What happens if we call #value: with an arbitrary value? Let’s try nil for now:

| selectBlock |
selectBlock := [ :customer | 
((customer surname is: 'Schneider') or: (customer surname is: 'Mueller'))
    and: ((customer bonusPoints gt: customer joinDate year) or: (customer joinDate year is: Date today year)) ].
expression := selectBlock value: nil.   "Inspect-it"

If we execute this snippet we’ll get an error message “MessageNotUnderstood: UndefinedObject>>surname“. And it’s clear why: Executing the block binds nil to customer. And the first message sent to customer is #surname. This of course raises an error because UndefinedObject does not understand #surname.

But what happens if we use another object (let’s call it a SQLTable) instead? This SQLTable does understand #surname and responds with something useful - a SQLColumn named accordingly in this case. If we keep up resolving to “useful” objects we’ll end up with a graph of objects expressing the original expression!

The “hard” parsing work is done by the Smalltalk compiler itself. Our job is only to record any (useful) message sent to our objects and respond with other useful objects to continue the proccess. Once we’re finished we can then use this graph of objects to create our “translated” language.

SQL Translator

NOTE: The following code snippets should be enough to build some working code (Copy&Paste from the blog should work). If you want to see the complete code you can find it here: BlockParsers on SmalltalkHub.

SQL tables

We’ll add bits and pieces of code along with the blog entry. Always just enough to hit the next Debugger. This will give us enough clues about how to proceed:
The first class we need to create is SQLTable to bind to the customer Variable. Make it a subclass of SQLComponent. It also needs to store the table name in an instance variable:

Object subclass: #SQLComponent
    instanceVariableNames: ''
    classVariableNames: ''
    category: 'BlockParser-SQL'
SQLComponent subclass: #SQLTable
    instanceVariableNames: 'name'
    classVariableNames: ''
    category: 'BlockParser-SQL'

Add (instance creation) methods to set the table name:

SQLTable class>>#named: aString
    ^ self new
        setName: aString;
        yourself

SQLTable>>#setName: aString
    name := aString

Try our new class and call the block with it:

| selectBlock table |
selectBlock := [ :customer | 
((customer surname is: 'Schneider') or: (customer surname is: 'Mueller'))
    and: ((customer bonusPoints gt: customer joinDate year) or: (customer joinDate year is: Date today year)) ].
table := SQLTable named: 'customers'.
selectBlock value: table.   "Inspect-it"

Executing this snippet will result in an error because (again) #surname is not understood:
Wallback: <code>MessageNotUnderstood: SQLTable>>surname</code>

If customer in the block is an SQLTable instance (or to be more specific a table row) then the semantic meaning of customer surname is to get its surname property - or to stick with SQL to get a column with that name.

SQL columns

To make things easier we’ll intercept each unary message sent to a SQLTable instance and return an SQLColumn instance which knows its originating table and its name. Because columns can participate in relations we’ll create an SQLColumn class as subclass of SQLTerm:

SQLComponent subclass: #SQLTerm
    instanceVariableNames: ''
    classVariableNames: ''
    category: 'BlockParser-SQL'

SQLTerm subclass: #SQLColumn
    instanceVariableNames: 'table name'
    classVariableNames: ''
    category: 'BlockParser-SQL'

We also add methods to set the owning table and name:

SQLColumn class>>#table: aSQLTable name: aString
    ^ self new
        setTable: aSQLTable name: aString;
        yourself

SQLColumn>>#setTable: aSQLTable name: aString
    table := aSQLTable.
    name := aString

We also need to add behaviour to SQLTable to return an SQLColumn instance when it recieves an unknown unary message. So we’ll add that behavior do #doesNotUnderstand:

SQLTable>>#doesNotUnderstand: aMessage
    | selector |
    selector := aMessage selector.
    selector isUnary
        ifTrue: [ ^ SQLColumn table: self name: selector asString ].
    ^ super doesNotUnderstand: aMessage

NOTE: In a “real” implementation you might want to check the selector name. If its a known column name (you have the schema? Don’t you?) you’d return the column. Otherwise forward #doesNotUnderstand: to super.

SQL expressions

Running the snippet now yields an “SQLColumn(Object)>>doesNotUnderstand: #is:” error:
Wallback: <code>MessageNotUnderstood: SQLColumn>>is:</code>

We’ll implement #is: as an comparison operator in an SQLTerm. Every SQL term (columns included) might be combined with a constant or to another term by using an operator. An SQLExpression stores a left and right term as well as the operand (like =, <, >, +, -, *, …):

SQLTerm subclass: #SQLExpression
    instanceVariableNames: 'left operand right'
    classVariableNames: ''
    category: 'BlockParser-SQL'

SQLExpression class>>#left: leftTerm operand: aSymbol right: rightTerm
    ^ self new
        setLeft: leftTerm operand: aSymbol right: rightTerm;
        yourself

SQLExpression>>#setLeft: leftTerm operand: aSymbol right: rightTerm
    left := leftTerm asSQLComponent.
    operand := aSymbol.
    right := rightTerm asSQLComponent

NOTE: Please note that we are sending #asSQLComponent to both terms here. The left term should always be a subclass of SQLComponent already. The right side however might also be a constant (originating from Smalltalk code). So sending #asSQLComponent provides the possibility to wrap constants in a SQLConstant (sub-)class.

SQLTerm subclass: #SQLConstant
    instanceVariableNames: 'value'
    classVariableNames: ''
    category: 'BlockParser-SQL'

SQLConstant>>#value: aValue
    ^ self new
        setValue: aValue;
        yourself

SQLConstant>>#setValue: aValue
    value := aValue

Now we need to implement #asSQLComponent in some classes which might appear in expressions:

SQLComponent>>#asSQLComponent
    ^ self

Object>>#asSQLComponent
    ^ SQLConstant value: self

NOTE: For now we only implement #asSQLComponent in Object and SQLComponent. In production you might want to use different SQLConstant subclasses for different kind of constants like Strings, Numbers, Dates to deal with the target expressions formatting.

Equality (#is:)

We’ll implement #is: in SQLTerm to return an SQLExpression.

SQLTerm>>#is: anObject
    ^ SQLExpression left: self operand: #= right: anObject

NOTE: Why do we use #is: instead of #=? Overriding #= instead of implementing #is: is a double edged sword. Especially in our case because we’d change the semantics of the message. We won’t return a Boolean any longer - we’ll return something different! Overwriting #= to answer a non-Boolean leads to interesting effects down the line … you have been warned …

Boolean Operators

Next try: Let’s see how far we get now.
Wallback; <code>MessageNotUnderstood: SQLExpression>>or:</code>

We’ll get an Error message “MessageNotUnderstood: SQLExpression>>or:“. So let’s implement SQLTerm>>#or: and SQLTerm>>#and:.

SQLTerm>>or: anObject
    ^ SQLExpression left: self operand: #| right: anObject

SQLTerm>>#and: anObject
    ^ SQLExpression left: self operand: #& right: anObject

NOTE: Our implementation does not use regular blocks as arguments. You can use blocks in your implementation though. Just be warned that the compiler/VM might inline sends of #and:, #or: … if the argument is a block!

NOTE: Logical #not is not an expression - not an operator “between” to terms. It’s an Operator applied to one term. So it’s best expressed as a function!

SQL functions

Running the code snippet complains about an SQLColumn instance not understanding #year. Semantically I’d say that something like tableName columnName year is like calling a function: YEAR(tableName.column).
So every unary message sent to an SQLTerm should result in a SQLFunction wrapping it:

SQLTerm subclass: #SQLFunction
    instanceVariableNames: 'name term'
    classVariableNames: ''
    category: 'BlockParser-SQL'

SQLFunction class>>#name: aString term: anSQLTerm
    ^ self new
        setName: aString term: anSQLTerm;
        yourself

SQLFunction>>#setName: aString term: anSQLTerm
    name := aString.
    term := anSQLTerm

We’ll also implement SQLTerm>>#doesNotUnderstand: to return SQLFunctions.

SQLTerm>>#doesNotUnderstand: aMessage
    | selector |
    selector := aMessage selector.
    selector isUnary
        ifTrue: [ ^ SQLFunction name: selector asString asUppercase term: self ].
    ^ super doesNotUnderstand: aMessage

NOTE: #doesNotUnderstand: is the quick and dirty solution here. If you have a limited number of functions you can also implement them as methods directly.

Comparisons

And again:
Wallback; <code>MessageNotUnderstood: SQLExpression>>gt:</code>

We’ll get an Error message “MessageNotUnderstood: SQLExpression>>gt:“. So the next method we need is greater than. We’ll implement these using similar to SQLTerm>>#is::

SQLTerm>>#gt: anObject
    ^ SQLExpression left: self operand: #> right: anObject

SQLTerm>>#gte: anObject
    ^ SQLExpression left: self operand: #>= right: anObject

SQLTerm>>#lt: anObject
    ^ SQLExpression left: self operand: #< right: anObject

SQLTerm>>#lte: anObject
    ^ SQLExpression left: self operand: #<= right: anObject

DONE! (1st half …)

We made it! Our expression parses! Inspecting the result of our snippet in the inspector shows a nice graph of objects which we’ll use in the next step to create the SQL String.
Parsed <code>SQLExpression</code>: Look Ma! Without any grammar!

SQL Generator

Now that we have a nice graph of objects let’s try to create the SQL string from it: Implement the messages #sqlString and #printSqlOn: in SQLComponent which should be implemented by all subclasses:

SQLComponent>#sqlString
    ^ String streamContents: [ :stream | self printSqlOn: stream ]

SQLComponent>#printSqlOn: aStream
    ^ self subclassResponsibility

Now let’s try our “implement until next error” approach again using the following code:

| selectBlock table expression |
selectBlock := [ :customer | 
((customer surname is: 'Schneider') or: (customer surname is: 'Mueller'))
    and: ((customer bonusPoints gt: customer joinDate year) or: (customer joinDate year is: Date today year)) ].
table := SQLTable named: 'customers'.
expression := selectBlock value: table. "Inspect-it"
expression sqlString    "Inspect-It"

We’ll get an error “SubclassResponsibility: SQLExpression had the subclass responsibility to implement #printSqlOn:“:
<code>SubclassResponsibility: SQLExpression had the subclass responsibility to implement #printSqlOn:</code>

So Pharo is telling us exactly what to do next. From now on we’ll simply implement #printSqlOn: in all the classes until we finally get the string without error.

SQLExpression>>#printSqlOn: aStream
    aStream nextPut: $(.
    left printSqlOn: aStream.
    aStream
        space;
        nextPutAll: operand;
        space.
    right printSqlOn: aStream.
    aStream nextPut: $)

As you can see we simply output the information either directly or by delegating #printSqlOn: to child nodes.

SQLColumn>>#printSqlOn: aStream
    table printSqlOn: aStream.
    aStream
        nextPut: $.;
        nextPutAll: name
SQLTable>>#printSqlOn: aStream
    aStream nextPutAll: name
SQLConstant>>#printSqlOn: aStream
    aStream print: value
SQLFunction>>#printSqlOn: aStream
    aStream
        nextPutAll: name;
        nextPut: $(.
    term printSqlOn: aStream.
    aStream nextPut: $)

Done!

Finally our translator works and yields

(((customers.surname = 'Schneider') | (customers.surname = 'Mueller')) | ((customers.bonusPoints > YEAR(customers.joinDate)) | (YEAR(customers.joinDate) = 2014)))

Cool, eh?

Summary

I hope I was able to show you (in an understandable way?) how to use “Block Parsers/Translators” to parse Smalltalk expressions and translate them into something “different”. I know that this example is neither comprehensive nor production ready. In a production setup you’d have to think a lot more about different subclasses e.g. for constants, functions … even if it’s “just” for printing constants correctly. But the skeleton should be the same.

Limitations/Notes

Method names

Overriding some methods (esp. #=) is a pretty bad idea. I agree that customer name = 'Schneider'is easier to read and write than customer name is: 'Schneider' - but trust me. Overriding #= with different semantics is a sure recipe for disaster!

You should also be careful with “Boolean-ish” methods like #and:, #or:, #ifTrue:. These methods are sometimes inlined by the compiler and you’ll get warnings about one of the operands being a non-Boolean.

Order of expressions

The whole approach bases on the idea of intercepting messages sent to an object (to be able to respond with “another” intercepting object). So make sure that in each and every expression the objects you put into the block (or derivates thereof) are always the recieving objects (left side in operations). Everything else will fail.

Two expressions might be semantically identical/equal in Smalltalk yet yield different results when used with Block Parsers. E.g.:

table := SQLTable named: 'customers'.

"Both blocks are semantically equal in Smalltalk ..."
block1 := [ :customer | customer age > 23 ].
block2 := [ :customer | 23 > customer age ].

"But not when used to parse!"
String streamContents: [ :stream | (block1 value: table) printSqlOn: stream ].  '(customers.age > 23)' .
String streamContents: [ :stream | (block2 value: table) printSqlOn: stream ]. "Error: SQLColumn(Object)>>doesNotUnderstand: #adaptToNumber:andSend:"

Expressions only! … mostly …

This approach does work fine if you want to translate an expression - even a compound one. Expressions (e.g. for filtering) are traditionally used for Collection messages like #select:. So something like this works fine (note the temporal variables):

| selectBlock table expression |
selectBlock := [ :customer | 
    | surname joinDate |
    surname := customer surname.
    joinDate := customer joinDate.
    ((surname is: 'Schneider') or: (surname is: 'Mueller'))
        and: ((customer bonusPoints gt: joinDate year) or: (joinDate year is: Date today year)) ].
table := SQLTable named: 'customers'.
expression := selectBlock value: table. "Inspect-it"
expression sqlString    "Inspect-It"

Something like this won’t work (as expected?):

| selectBlock table expression |
selectBlock := [ :customer | 
    | surname |
    surname := customer surname.
    surname is: 'Schneider'.
    surname is: 'Mueller' ].
table := SQLTable named: 'customers'.
expression := selectBlock value: table. "Inspect-it"
expression sqlString    "Inspect-It" " (customers.surname = 'Mueller')'"

Only the expression for the second use surname is: 'Mueller' is returned an can be translated. You can of course use a builder in the background and record “new” expressions - i.e. if the initial object passed in receives a message. But that’s not 100% safe - especially if you didn’t refactor all temp variables.

But if you stick to expressions in Blocks (although it also works fine for expressions in methods!) it’s more likely to not hit that limitation.

Priort Art

By no means did I invent this stuff! … that’s at least what I think. Based on frameworks I worked with and some feedback I got I’m aware of at least two places, where this approach has been used before:

AFAIK both frameworks use a similar approach to create SQL queries from Smalltalk blocks.

Written with StackEdit.

Friday, August 08, 2014

Replacing Floating Point multiplication with Integer shifting (or ... "optimization witchcraft")

Updated 2014/08/09 (see update)

NOTE: Throughout this article I try to use lowercase names (i.e. float or integer) for the types and uppercase names (i.e. Float or Integer) for class names.

I’m currently working with some professional vision mixers and one of the tasks is loading & saving image from and to the mixer. And the mixer expects all in 8-bit (4:2:2) encoded YCbCr. Converting between RGB and YCbCr is pretty straight forward using some transformation matrices:

RGB=1.1641.1641.16400.3922.0171.5960.8130Y16Cb128Cr128

floatRgbFromY: y Cb: cb Cr: cr
    "YCrCb to RGB
    RGB 0-255
    Y 16-235
    CbCr 16-240"

    | r g b |
    r := (y - 16) * 1.164 + ((cr - 128) * 1.793).
    g := (y - 16) * 1.164 + ((cb - 128) * -0.213) + ((cr - 128) * -0.533).
    b := (y - 16) * 1.164 + ((cb - 128) * 2.112).
    ^ {r.g.b}

However using this code to convert a 1280x720 image from YCbCr takes around 20 seconds on my machine … not really fast. After some surfing I found a two different ways to convert the data - both of which where a bit and much faster:

integerRgbFromY: y Cb: cb Cr: cr
    "YCrCb to RGB
    RGB 0-255
    Y 16-235
    CbCr 16-240"

    | ym cbm crm r g b |
    ym := (y - 16) * 149 / 128.
    cbm := cb - 128.
    crm := cr - 128.
    r := ym + (crm * 459 / 256).
    g := ym - (cbm * 109 / 512) - (crm * 17 / 32).
    b := ym + (cbm * 135 / 64).
    ^ {r.g.b}
shiftRgbFromY: y Cb: cb Cr: cr
    "YCrCb to RGB
    RGB 0-255
    Y 16-235
    CbCr 16-240"

    | ym r g b cbm crm |
    ym := y - 16.
    ym := ym + (ym >> 3) + (ym >> 5) + (ym >> 7).
    cbm := cb - 128.
    crm := cr - 128.
    r := ym + crm + (crm >> 3) + (crm >> 4).
    g := ym - ((cbm >> 3) + (cbm >> 4) + (cbm >> 5)) - ((crm >> 1) + (crm >> 5)).
    b := ym + ((cbm << 1) + (cbm >> 4) + (cbm >> 5) + (cbm >> 6)).
    ^ {r.g.b}

To be honest I thought I understood the integer approach but had no idea how the shift approach worked. Still the results were the same numerically - just a lot faster. So I my adventure into “Integer witchcraft” started and I decided to keep my findings here in the blog.

I’ll start with a simple example. Lets take the term x1.164. This is obviously a term which requires floating point operations. Lets try to convert it into an integershift(s) expression step by step.

Eliminate floating point numbers (using powers of 10)

The float 1.164 is something we want to eliminate. Because it has a limited number of decimal places it’s easy to rewrite it as a combination of one multiplication and one division. I.e.

x1.164=x11641000=x1164÷1000=x÷10001164

The last two terms are mathematically equal – however if you work in a language where integeroperations do not coerce to floats “automagically” (e.g. C or Ruby) you my want to multiply first. Why? Let’s assume x=10 then

(int)x÷(int)1000(int)1164(int)10÷(int)1000(int)1164(int)0(int)1164(int)0(int)x(int)1164÷(int)1000(int)10(int)1164÷(int)1000(int)11640÷(int)1000(int)11

So multiplying first doesn’t hurt in Smalltalk (unless you sprinkle in a lot of asInteger calls) or other languages which automatically coerce to floats if needed … but might safe your bu.. in C, Ruby and maybe a few others.

Eliminate floating point numbers (using powers of 2)

Instead of using powers of 10 we can also use powers of 2. This will allow us to convert the expression x1.164 into an Integer-only/shifting expression.

We can use any power of 2 – but let’s just use 32 (25) for now. We can/will/should/must use others as well; but that’s discussed later.

x1.164=x1.1641=x1.1643232=x1.16432÷32

1.164 is equal to 1.16432÷32 and with a bit of integer magic we can come up with an integer expression which is “kind of” equal:

1.164=1.16432÷32(int)(1.16432)÷(int)3237÷32=1.15625

As you can see the difference between the float value 1.164 and our approximate “equivalent” expression value 1.15625 is quite small. But it’s a lot easier (and faster) to calculate x37÷32 than x1.164.

When working in languages which to not automatically coerce the result of integer operations to floats when needed your can stop reading here. Integer arithmetic is on of the most heavily optimized areas in today’s compilers and CPUs.
It’s different in Smalltalk though: A simple expression like 3 * 4 / 5 (which would be 2with integer arithmetic and 2.4with floating points) might result in a Fraction ((12/5))!!! Although great from a “keep the precision” standpoint it’s a speed nightmare. Sprinkling in some asFloatcalls might speed up the thing a bit … but for soeme calculations it can even be faster … just read on.

Replace multiplication of floating point numbers with integer shifts

So how to convert the expression x37÷32 into something which only uses integer shifts? The “trick” is to replace the numerator 37 with expressions which are powers of 2 (the denominator is already a power of 2). Each of these expressions is either a multiplication or division with a power of 2.

QUICK REFRESH
xs=x2s: Shifting an integer x by s bits to the left is equal to multiplying x with 2s.
xs=x2s=x÷2s: Shifting an integer x by s bits to the left is equal to multiplying x with 2s or dividing by 2s.

x37÷32=========x(32+4+1)÷32x(25+22+20)÷25x(25+22+2025)x(2525+2225+2025)x(1+123+125)x(20+23+25)(x20)+(x23)+(x25)(x0)+(x3)+(x5)x+(x3)+(x5)

So we can replace the expression x1.164 (which “forces” float values&operations) with x+(x3)+(x5) (which only uses integer values&operations).

Conclusion

Maybe everybody knew this “trick” and I have simply been living under a rock for the last decades. If this is the case this blog still server of a reminder for myself. If you indeed learned something that’s even better!

Limitations

IT ONLY WORKS FOR INTEGER VALUES!!

An expression like x1.164 can only be converted to x+(x3)+(x5) if any only if x is an integer!

PRECISION

Float values (x) can be represented as a fraction (ab). Other floats (e.g. π) cannot be represented as a fraction. The method presented above however will always try to approximate the float value x with a fraction. Even if the value can be represented as a fraction (x) you might loose precision – due to the denominator always being a power of 2 and because the achievable precision depends on the used exponent:

Denominator 16=24

  • Approximated fraction: 1.1641916=1.1875; Error 0.02350
  • Shift Expression: x + (x >> 3) + (x >> 4)

Denominator 32=25

  • Approximated fraction: 1.1643732=1.15625; Error 0.00775
  • Shift Expression: x + (x >> 3) + (x >> 5)

Denominator 64=26

  • Approximated fraction: 1.1647464=1.15625; Error 0.00775
  • Shift Expression: x + (x >> 3) + (x >> 5)

Denominator 128=27

  • Approximated fraction: 1.164149128=1.1640625; Error 0.00006
  • Shift Expression: x + (x >> 3) + (x >> 5) + (x >> 7)

So in theory the bigger the denominator the higher the precision – although not every step means more precision (compare 32 and 64). Another limiting factor is the numeric range of the variable. If the variable is an unsigned byte (0-255) it’s pointless to shift it more than 8 bits to the right.

So given the example above (1.164) using 128 for byte-sized values is pointless: The largest shift is 7 bits – so only values with the highest bit set (128+) will “survive” and result in a value different than 0. Using 64 or 32 will result in the same shift operations with a maximum shift of 5 bits - so the highest 3 bits will “survive”. That’s quite usable for most cases.

Finding the best compromise between precision and number of shifts is the actual hard decision you have to make. Check the code below to make an informed decision.

Code

NOTE: The code below is neither nice nor fast. But it does it’s job :-)

Number>>#multiplyAsShiftReportWith
    ^ self multiplyAsShiftReportWith: 'x'
Number>>#multiplyAsShiftReportWith: variableName
    ^ String
        streamContents: [ :report | 
            | denominator numerator aproximatedFloat bitString numberOfSetBits currentShiftOffset shiftPositions |
            report
                nextPutAll: 'Float: ' , self printString;
                cr.
            4 to: 9 do: [ :denominatorExponent | 
                denominator := 2 raisedTo: denominatorExponent.
                numerator := (self * denominator) rounded.
                aproximatedFloat := (numerator / denominator) asFloat.
                bitString := numerator bitString last: 16.
                numberOfSetBits := bitString asBag occurrencesOf: $1.
				report
					cr;
					nextPutAll: ('<1p> / <2p> = <3p>' expandMacrosWith: numerator with: denominator with: aproximatedFloat);
					cr;
					nextPutAll:
							('|Error| = <1s>; (log10 |Error| = <2s>)'
									expandMacrosWith: ((aproximatedFloat - self) abs printShowingDecimalPlaces: 5)
									with: ((aproximatedFloat - self) abs log printShowingDecimalPlaces: 3));
					cr;
					nextPutAll: ('<1p> = Binary <2s>' expandMacrosWith: numerator with: bitString);
					nextPutAll: ('; required shifts: <1p>' expandMacrosWith: numberOfSetBits);
					cr;
					nextPutAll:
							('Precision/Shifts Ratio: <1s>'
									expandMacrosWith: ((aproximatedFloat - self) abs log abs / numberOfSetBits printShowingDecimalPlaces: 3));
					cr;
					nextPutAll: ('Orignal Expression: <1s> * <2p>' expandMacrosWith: variableName with: self);
					cr;
					nextPutAll:
							('Integer Expression: <1s> * <2p> / <3p>' expandMacrosWith: variableName with: numerator with: denominator);
					cr.
				currentShiftOffset := denominatorExponent - bitString size.
				shiftPositions := OrderedCollection new.
				bitString asArray
					do: [ :bit | 
						currentShiftOffset := currentShiftOffset + 1.
						bit = $1
                            ifTrue: [ shiftPositions add: currentShiftOffset ] ].
                report nextPutAll: 'Shift Expression: '.
                shiftPositions
                    do: [ :position | 
                        position = 0
                            ifTrue: [ report nextPutAll: variableName ]
                            ifFalse: [ 
                                position negative
                                    ifTrue: [ report nextPutAll: ('(<1s> %<%< <2p>)' expandMacrosWith: variableName with: position negated) ]
                                    ifFalse: [ report nextPutAll: ('(<1s> >> <2p>)' expandMacrosWith: variableName with: position) ] ] ]
                    separatedBy: [ report nextPutAll: ' + ' ].
                report cr ] ]

Code (Usage)

I using the same float (1.164) I used throughout this article to demonstrate the functionality. The report shows the different values incl. their precision, number of shifts and expressions which can be directly copy&pasted.

1.164 multiplyAsShiftReportWith: 'x'. "print-it"
 'Float: 1.164

19 / 16 = 1.1875
|Error| = 0.02350; (log10 |Error| = -1.629)
19 = Binary 0000000000010011; required shifts: 3
Precision/Shifts Ratio: 0.543
Orignal Expression: x * 1.164
Integer Expression: x * 19 / 16
Shift Expression: x + (x >> 3) + (x >> 4)

37 / 32 = 1.15625
|Error| = 0.00775; (log10 |Error| = -2.111)
37 = Binary 0000000000100101; required shifts: 3
Precision/Shifts Ratio: 0.704
Orignal Expression: x * 1.164
Integer Expression: x * 37 / 32
Shift Expression: x + (x >> 3) + (x >> 5)

74 / 64 = 1.15625
|Error| = 0.00775; (log10 |Error| = -2.111)
74 = Binary 0000000001001010; required shifts: 3
Precision/Shifts Ratio: 0.704
Orignal Expression: x * 1.164
Integer Expression: x * 74 / 64
Shift Expression: x + (x >> 3) + (x >> 5)

149 / 128 = 1.1640625
|Error| = 0.00006; (log10 |Error| = -4.204)
149 = Binary 0000000010010101; required shifts: 4
Precision/Shifts Ratio: 1.051
Orignal Expression: x * 1.164
Integer Expression: x * 149 / 128
Shift Expression: x + (x >> 3) + (x >> 5) + (x >> 7)

298 / 256 = 1.1640625
|Error| = 0.00006; (log10 |Error| = -4.204)
298 = Binary 0000000100101010; required shifts: 4
Precision/Shifts Ratio: 1.051
Orignal Expression: x * 1.164
Integer Expression: x * 298 / 256
Shift Expression: x + (x >> 3) + (x >> 5) + (x >> 7)

596 / 512 = 1.1640625
|Error| = 0.00006; (log10 |Error| = -4.204)
596 = Binary 0000001001010100; required shifts: 4
Precision/Shifts Ratio: 1.051
Orignal Expression: x * 1.164
Integer Expression: x * 596 / 512
Shift Expression: x + (x >> 3) + (x >> 5) + (x >> 7)
'

Update 1

This approach of course works for every kind of Number, ScaledDecimals included (thanks Tobias!). So I moved the method to class Numberand updated the code.

Update 2

Thanks to a Twitter conversation with Hwa Jong Oh there is now a FastConstantMultiplier. So if you need to multiply an Integer with a constant quite often this might be interesting for you:

Load package

Gofer it
    smalltalkhubUser: 'UdoSchneider' project: 'Playground';
    package: 'FastConstantMultiplier';
    load.

Using the package

m := FastConstantMultiplier  constant: 0.123456789 significantDigits: 11.

m * 10000. "1232 "
m * 10000000000000." 1234567890054" 

Written with StackEdit.