Log in

No account? Create an account
Journal new. [entries|archive|friends|userinfo]

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Fast Luhn-digit generation algorithm [okt. 16-a, 2005|12:48 pm]
[Tags|, ]
[Nuna humoro |relaxedrelaxed]
[Nuna muziko |Comalies (Lacuna Coil)]

I referenced the Luhn mod-10 check for credit card numbers in my last post.

The fastest implementation I'd encountered so far was my dad's, which was also pleasantly simple.

The weird part about the Luhn algorithm, from the point of view of a modern binary computer, is that it's oriented toward base-10 digits. One step of the algorithm doubles each second digit, and adds the digits of the result together until one digit remains. Popular with numerologists, but semi-complex if your data is in binary.

My dad simply built a table of 10 integers, containing the result of doubling-and-adding each possible digit — in other words, { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 }. In hindsight, this is a pretty obvious optimization, but boy, does it speed things up.

I've taken it a step farther. Here's mine in pseudocode.

deltas := { 0, 1, 2, 3, 4, -4, -3, -2, -1, 0 }.
sum := the sum of all digits in the input.
for every other digit d in the input:
sum := sum + deltas[d].

check := 10 - (sum mod 10).

The deltas array contains the correction for doubling the digits — the difference between adding the digit straight, and adding it with the double-and-add algorithm.

In C, this is 150% faster than the original (already fast) implementations. It also lends itself reasonably well to Altivec optimization, not that it really matters, since the input data sets are so small.

The strange thing? I've seen a lot of Luhn implementations. I've never seen anyone do this. Weird.
Ligilo3 komentoj|Afiŝu novan komenton

Generating large numbers of valid credit card numbers for fun and !profit. [okt. 15-a, 2005|07:32 pm]
[Nuna muziko |random cafe jazz]

So, let's say you need a Java program to generate a large number of "valid" credit card numbers quickly. The credit card numbers need to be passed into another function as 16-position byte arrays filled with base-10 ASCII digits.

By "valid" numbers, I mean that they're of appropriate length, format, BIN, and meet the Luhn mod-10 check. They may or may not map to an actual credit card number.

This would be useful if one were, hypothetically, brute-force colliding an SHA-1 hash on a Saturday night to prove a point. But I digress.

How best to do it?

The evolution of an algorithmCollapse )

Using the current semi-final algorithm, my little iBook can generate a valid number per 27ns — a sustained throughput rate of 565MB/sec.

Anyone have any additional suggestions?

LigiloAfiŝu novan komenton

Java splash screens. Yay. [sep. 30-a, 2005|01:02 pm]
Through a convoluted circuit of weblogs, I discovered an article on the new Splash Screen functionality that's going into Java 1.6/6.0/60/whatever.

To cut to the chase, I think this is a spectacularly bad idea. For a more involved discussion, see the dialog with the article that follows:

Splash screens are a standard part of any modern graphical user interface (GUI) application.

That's stretching the definition of the word "modern." Splash screens are a part of many GUI applications that have poor startup times. They are frequently modal, which irritates the hell out of those of us trying to multitask.

Their primary purpose is to let the user know that the application is starting up. An application that displays a polished and professional-looking splash screen can occupy the user's attention and gain the user's confidence that the application is starting.

Once upon a time, my Nova was having engine problems. It would often require several seconds of pumping the gas and holding the ignition before it would start. According to the theory referenced here by Sun, the solution to this would be a happy little "I'm starting!" light on the dashboard, to "gain the user's confidence" by reassuring me that, yes, the car would eventually start.

In the real world, of course, the solution is to make the car start when I tell it to, dammit, and the same goes for software. Splash screens are a useless distraction from the slow application startup, which itself is consuming what could be productive time.

Sure, there's going to be some latency at startup for any application, but proper design can minimize the effects. Cesta, my network analysis app (which is progressing slower now that I have an actual job), starts up nigh-instantaneously on outdated hardware, because of a number of techniques (most of which have the word "lazy" in their name).

The user should be able to get to a productive point as quickly as possible, even if the application is still loading stuff in the background.

Now, this does tend to be difficult in Java, for a number of reasons, but Sun should be addressing that issue, not giving us splash screen libraries.
LigiloAfiŝu novan komenton

Palm is dead. [sep. 25-a, 2005|11:28 am]
[Tags|, , ]
[Nuna muziko |Run On (Moby)]

Well, Palm (the hardware company) released a Treo running WinCE.

I think this is probably the death-knell for the Palm platform, in the sense of PalmOS. I have mixed feelings on this.

On the one hand, I've always considered Palm to be far superior to WinCE for organization and such. Even on underpowered hardware, it was always so much more responsive, largely because it never had to shuffle data around in memory. (Programs and data ran out of their storage space.)

On the other hand, the Palm platform has not advanced since, arguably, 4.0. Sure, 5.0 introduced some snazzy new APIs and ARM compatibility — but most user code is still 68k. If you want to take advantage of the ARM processor (without an emulation layer), you have to write these odd little code fragments called ARMlets, and miss out on most of the system API that makes Palm so powerful.

Not to mention the fact that there's still no solid support for background tasks, memory protection, or modern languages. I run a third-party Java VM on my Tungsten C, but it, like ARM code, can't access the APIs. Gotta code in 68k C for that.

It might be that Palm has been dead for several years, continuing only out of momentum. That's sure what their new-sale market share suggests. But it makes me sad. Some tasks are particularly well-suited for a handheld computer, but WinCE is (ironically) not. Nor is Linux, in many ways.

LigiloAfiŝu novan komenton

Python is strange. [sep. 23-a, 2005|11:20 am]
Python's doing something weird to me.

I can't really blame it, because I'm sure as hell doing something weird to it.

Given the following code:
array = [1, 2, 3, 4, 5]
funcs = [(lambda y: x * y) for x in array]

...one would think funcs would contain five functions, which would each multiply their sole argument by a number between 1 and 5.

So, then, what do we get from this:
[foo(2) for foo in funcs]

Should print [2, 4, 6, 8, 10] — we're evaluating each function, in sequence, with the integer 2 as the argument.

What does it print?
[10, 10, 10, 10, 10]

But if you print the funcs array, you see that the five lambdas are, indeed, distinct and separate objects!

It seems all the lambdas bind to the same variable, temporarily named x, which is updated each iteration. This strikes me bad, or at least counterintuitive.

I sincerely hope there's a cleaner way of doing this, but here's the easiest way I've found to make it work:
funcs = [eval("lambda y : %s * y" % str(x)) for x in array]


I'm sure some Pythonite out there can explain to me why this makes sense. I'd like to hear it. After that, please explain the results of this one:
[x(2) for x in [(lambda y: x * y) for x in [1,2,3,4,5]]]

(Nested lexical scopes my ass.)
LigiloAfiŝu novan komenton

Source to the AddressBook SIM example [sep. 22-a, 2005|11:03 am]
[Tags|, , ]
[Nuna humoro |amusedamused]
[Nuna muziko |Jolene (Cake)]

Here's the full example sources — SIM and Java — for the AddressBook example.

This does not include the SIM sources. You won't be able to build this. But it makes for interesting reading.

Sources!Collapse )

The end result? Click the button, a person is added to the list, the table updates instantly, etc. It just works.

LigiloAfiŝu novan komenton

A more interesting SIM example [sep. 21-a, 2005|09:55 am]
[Tags|, , ]
[Nuna humoro |amusedamused]
[Nuna muziko |Honey (Moby)]

Here's a slightly more interesting SIM example. This one presents a traditional master-detail interface for a simple address book.

New features:

  • Splitters, which provide a draggable divider between two components.
  • Tables, which are lists of items with multiple columns.
  • Bindings between UI components themselves, instead of direct to the controller.

<?xml version="1.0"?>
<s:sim-ui xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
          xsi:schemaLocation="http://www.cliff.biffle.org/sim/ui.xsd ./sim.xsd">

    <!-- A vertical splitter presents two components, one above the other. -->
    <s:splitter axis="vertical" id="addressPanel">

        <!-- The table gets its data from the owner's 'people' property,
             and provides a virtual bean called 'person' for each row to bind to. -->
        <s:table id="peopleList" var="person"
            <s:tableColumn name="Name" value="#{person.name}"/>
            <s:tableColumn name="Phone" value="#{person.phone}"/>

        <s:grid columns="2">
            <s:col autosize="false"/>
            <s:col autosize="true"/>

            <!-- The text fields bind to properties of the table's selectedObject object,
                 causing them to update as the selection changes. -->
            <s:label for="name" value="Name:" mnemonic="n"/>
            <s:textField id="name" value="#{peopleList.selectedObject.name}"/>
            <s:label for="phone" value="Phone:" mnemonic="p"/>
            <s:textField id="phone" value="#{peopleList.selectedObject.phone}"/>


I'll post a demo JAR once I'm not at work (no external ssh here). For now, some details:

  • The table cells and text fields automatically become editable or non-editable, depending on whether their bound property can be changed.
  • All the same two-way bound-property mojo from the last example exists here. That is, for editable properties, the table cells affect the text fields, the text fields affect the table cells, and programmatic updates affect both.
  • Column sorting in the table will work soon. Swing makes this marginally more difficult than it should be (though, I would argue, not as difficult as Cocoa).

LigiloAfiŝu novan komenton

SIM: Simple Interface Markup [sep. 19-a, 2005|07:02 pm]
[Tags|, , ]
[Nuna muziko |No Education (Apocalyptica)]

Over the past few months, I've been working with JavaServer Faces. As with any 1.0 technology, it has its share of warts — but despite them, it really is a generational advance over and above previous frameworks.

I've also been doing a lot of Cocoa development, using Xcode and Interface Builder.

Then, I tried to put together a Swing app. DEAR GOD. And to think I used to do Swing development for a living!

So, as I mentioned in a previous post, I've been working on desuckifying Swing. Here's my opening volley.

Allow me to present SIM, Simple Interface Markup. SIM allows you to define your user interface using a simple XML structure, and dynamically bind it to your controller and model layers.

SIM uses basically the same model as Cocoa NIB files, with a binding architecture inspired by JSF. As an example, here's a Fahrenheit-Celsius temperature converter, stolen from Apple's Cocoa Bindings examples. This is written in a very preliminary dialect of SIM, but it works:

<?xml version="1.0"?>
<s:sim-ui xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
        xsi:schemaLocation="http://www.cliff.biffle.org/sim/ui.xsd ./sim.xsd">
   <s:grid columns="2">
      <s:col autosize="false"/>
      <s:col autosize="true"/>
      <s:label for="degreesF" value="F:" mnemonic="f"/>
      <s:textField id="degreesF" value="#{fahrenheit}"/>
      <s:slider min="-40" max="300" value="#{fahrenheit}"/>
      <s:label for="degreesC" value="C:" mnemonic="c"/>
      <s:textField id="degreesC" value="#{celsius}"/>
      <s:slider min="-40" max="300" value="#{celsius}"/>

A dissection:
- The grid element defines a display panel (in the Swing implementation, a JPanel) with the specified number of columns. Layout is much like an HTML table: columns and rows expand as needed to house their contents.
- The col elements (which are optional) specify that the second column should autosize as the panel is resized.
- The label, textField, and slider elements declare UI controls. The textField and slider controls in this example use value bindings to two properties, "fahrenheit" and "celsius."
- The spacer element simply eats a position in the grid.

Like NIBs in Cocoa, the SIM file is instantiated at runtime with a particular object as its owner. All bound properties (like "fahrenheit" and "celsius") are connected to this owner object through standard JavaBeans methods. Using a simple F/C converter bean, one can drag the sliders and watch everything update in real-time.

If you've done this in Swing, you'll probably recognize how much work we just saved. (Hint: clubbing GridBagLayout into doing what we want, writing event listeners to keep properties in sync without excessive method calls, doing value conversions and validation to/from the model objects.)

And unlike a certain offense against nature *coughJSF-on-JSPcough*, the "for" attribute on the labels will work even if the labels come before their peer components. :-)

I'm packaging up a demo, which will appear here when ready.
Ligilo2 komentoj|Afiŝu novan komenton

JFrame minimum size stupidity! [sep. 14-a, 2005|08:59 pm]
I'm writing a neat library. It lets you define a UI in simple, JSF-inspired XML, and use Cocoa-inspired bindings to connect it to your controller and model objects.

Basically, it aims to take the suck out of Swing.

But that's proving more difficult than anticipated. It's clear to me that the Swing layout managers, in particular, weren't designed test-first. It's not just that they don't lend themselves to a specific use — they really don't lend themselves to use, in general. Doing the World's Most Common UI Layout — controls with text labels on the left — is surprisingly difficult.

But that's nothing.

I discovered, with the working prototype of my engine in hand, that JFrames will happily shrink to tiny sizes. They seem to totally ignore the "minimum size" of their contents. They have a setMinimumSize() method that does nothing.


The recommended method? Register a ComponentListener with the JFrame, which will get notification when the size changes. If the size is outside your desired bounds, set it back.

Yay. If the system is slow enough (or on the Mac, where the UI updates strangely), you can visibly see the frame bounce between sizes.
LigiloAfiŝu novan komenton

Safari's WebArchive format [sep. 10-a, 2005|01:27 pm]
[Tags|, , , ]
[Nuna humoro |amusedamused]
[Nuna muziko |Mi Linda (Los Amigos Invisibles)]

I've seen several discussions online about Safari's WebArchive format (new in 10.4).

This thread on CocoaBuilder claims the byte-level format is proprietary, but that you can load them with the WebArchive class in WebKit.

An entry from Paul Thurrott's blog (search for Safari, the permalink is broken) claims that Safari's WebArchive format is Safari-proprietary just like IE's.

Seriously. Does nobody use a hexeditor anymore?

It took me about 30 seconds to determine that Safari's WebArchive is, in fact, a standard Mac OS X plist file, albeit in the new binary encoding (introduced in Tiger along with WebArchives). To confirm this, save any page as a WebArchive (Safari: File -> Save As, choose Web Archive as the format). Then, with this file (which we'll call foo.webarchive), do this:

open -a 'property list editor' foo.webarchive

Alternatively, you can rename the file to foo.plist and double-click it.

Either way, if you've got the developer tools installed, you'll get the WebArchive open in tree format. Here's what my sample contains:

/WebMainResource/WebResourceData: a binary data chunk containing the page source exactly as received. Property List Editor (the worst program on the Mac) presents this only as a string of hex digits; pipe this through xxd -r -p to decode.
/WebMainResource/WebResourceMIMEType: the mime type of WebResourceData, as described by the server.
/WebMainResource/WebResourceTextEncodingName: the text encoding used in WebResourceData. This is only apparent for text data, like HTML.
/WebMainResource/WebResourceURL: the URL from which the resource was originally retrieved.
/WebSubResources: an array of dictionaries describing linked objects, each of which contains identical keys to the /WebMainResource dict.

I'm working on a tool to manipulate these from the command line, just to prove my point.

This isn't exactly an open format, but at least it's an obvious format. Hooray obvious formats!

Update: With my new command-line WebArchive tools in hand, I've discovered that there's an additional key in each WebSubResources entry: WebResourceResponse. It contains -- get this -- another binary plist file, embedded as binary data.

The embedded plist is actual serialized ObjC objects respresenting the server response.

I'm working on code to deserialize and inspect them now.
Ligilo1 komento|Afiŝu novan komenton

[ viewing | most recent entries ]
[ go | earlier ]