Yann's Blog - Software and hardware

Success!

I give you the first half of a market order cache file, including RLE decompressed database rows. The structure is not 100% correct in regards to nested elements, and there is a bit of unresolved magic occurring at the substream end condition. Also, the naming of the elements is somewhat odd – the first set of orders is actually the Sell orders, and the second half comprises the Buy orders. The exact meaning of the header defining the structure is also not yet determined (suspect its an identifier followed by a numerical “type” code, though either the order differs from the row descriptor or the types have no relation to the serialized types in the cache file…).

The second half of the file can be parsed (except for the odd end condition again…), but the nesting structure is “broken”. This will require some more investigation, but is likely easy to fix.

Another oddity is the dictionary type (or double tuple – the length is half of the number of elements present). It is encoded value followed by key (not key followed by value).

Below is the AST structure dump from the ‘dumper’ utility included. The cache files list Armageddons in Lonetrek as of a couple days ago.

 <SInt '738197504'>
 <STuple>
 (
   <SMarker ID: -120 >
   <SIdent 'GetOrders'>
   <SInt '10000016'>
   <SInt '643'>
 )
 <SDict>
 (
   <SObject>
   (
     <SIdent 'objectCaching.CachedMethodCallResult'>
     <STuple>
     (
       <SDict>
       (
         <STuple>
         (
           <SIdent '1 minute'>
           <NONE>
           <NONE>
         )
         <SIdent 'versionCheck'>
         <SMarker ID: -114 >
         <SIdent 'sessionInfo'>
       )
       <SSubstream>
       (
         <SLongLong '2678554370227830784'>
         <SString 'dbutil.RowList'>
         <SDict>
         (
           <SDBHeader>
           (
             <STuple>
             (
               <SString 'blue.DBRowDescriptor'>
               <STuple>
               (
                 <STuple>
                 (
                   <STuple>
                   (
                     <SMarker ID: -117 >
                     <SInt '6'>
                   )
                   <STuple>
                   (
                     <SMarker ID: -95 >
                     <SInt '5'>
                   )
                   <STuple>
                   (
                     <SMarker ID: 74 >
                     <SInt '2'>
                   )
                   <STuple>
                   (
                     <SMarker ID: -116 >
                     <SInt '2'>
                   )
                   <STuple>
                   (
                     <SMarker ID: -118 >
                     <SInt '3'>
                   )
                   <STuple>
                   (
                     <SMarker ID: -96 >
                     <SInt '3'>
                   )
                   <STuple>
                   (
                     <SMarker ID: -119 >
                     <SInt '3'>
                   )
                   <STuple>
                   (
                     <SMarker ID: 116 >
                     <SInt '11'>
                   )
                   <STuple>
                   (
                     <SMarker ID: -125 >
                     <SInt '64'>
                   )
                   <STuple>
                   (
                     <SMarker ID: 126 >
                     <SInt '2'>
                   )
                   <STuple>
                   (
                     <SMarker ID: -101 >
                     <SInt '3'>
                   )
                   <STuple>
                   (
                     <SMarker ID: -115 >
                     <SInt '3'>
                   )
                   <STuple>
                   (
                     <SMarker ID: -106 >
                     <SInt '3'>
                   )
                   <STuple>
                   (
                     <SMarker ID: 41 >
                     <SInt '3'>
                   )
                 )
               )
             )
           )
           <SMarker ID: 36 >
           <STuple>
           (
             <SMarker ID: -117 >
             <SMarker ID: -95 >
             <SMarker ID: 74 >
             <SMarker ID: -116 >
             <SMarker ID: -118 >
             <SMarker ID: -96 >
             <SMarker ID: -119 >
             <SMarker ID: 116 >
             <SMarker ID: -125 >
             <SMarker ID: 126 >
             <SMarker ID: -101 >
             <SMarker ID: -115 >
             <SMarker ID: -106 >
             <SMarker ID: 41 >
           )
           <SIdent 'columns'>
         )
         <DBRow 001882ba7d000000000000000000f03f509bcdfd85fcc90178a1af460500000001000000ac96930390969800d3c8c901050000008302ff7f5a>
         <DBRow 001882ba7d000000000000000000144050a0f97765fec901a105c54608000000010000007390930390969800d3c8c901050000008302ff7f5a>
         <DBRow f0c6933881000000000000000000f03f909da9a71a0eca019b048e480100000001000000468a930390969800d7c8c901010000008302ff7f5a000000>
         <DBRow 004ee77e7d000000000000000000f03f9067651cec00ca013b9b434701000000010000007192930390969800eec8c901070000008302ff7f5a000000>
         <DBRow 003476667b000000000000000000f03f300ef4eb3409ca0173a311480100000001000000c2bf930390969800eec8c901070000008302ff7f5a>
         <DBRow 001882ba7d000000000000000000f03f50b65d2fc40eca0143029f480100000001000000149b930390969800f2c8c901040000008302ff7f5a>
         <DBRow 001882ba7d000000000000000000f03f3024c3b6fc0eca01fe10a6480100000001000000149b930390969800f2c8c901040000008302ff7f5a>
         <DBRow 00e09962820000000000000000001440b0a9347fe3dec901ec889b3c0a00000001000000179b930390969800f3c8c901050000008302ff7f5a>
         <DBRow 00a8b10a870000000000000000000040e0883e7431e2c901039148440b000000010000000490930390969800f9c8c901070000008302ff7f5a>
         <DBRow 9ca7b10a8700000000000000000008404015505adcfdc9012b53f94606000000010000002296930390969800f9c8c901070000008302ff7f5a000000>
         <DBRow 8049016282000000000000000000f03f10c1e8bc0409ca01e9ad0e4801000000010000001996930390969800fbc8c901080000008302ff7f5a000000>
         <DBRow 00f94a8f7c0000000000000000001440c0a05632d10fca01fd20bb4805000000010000003796930390969800fdc8c901060000008302ff7f1e>
         <DBRow 809ddd657b000000000000000000084010aee06a2e10ca010c32c34803000000010000003796930390969800fdc8c901060000008302ff7f1e000000>
         <DBRow 7068e38f7c000000000000000000f03f20ffe8eced0aca012b523b4802000000010000003196930390969800fdc8c901060000008302ff7f5a000000>
         <DBRow 809ddd657b000000000000000000f03f1073931cab0fca01bda1354805000000010000003796930390969800fdc8c901060000008302ff7f1e000000>
         <DBRow 00267c907c000000000000000000f03fb0a3e34d050eca01c4d68a4801000000010000002e9693039096980001c9c901080000008302ff7f5a>
         <DBRow 0070c9b28b000000000000000000f03f50dfb0e8010fca0141d0a64801000000010000009d969303909698000fc9c9010a0000008302ff7f5a>
         <DBRow 8049016282000000000000000000f03f40a6e8b2240bca013434424801000000010000006f9793039096980010c9c901090000008302ff7f5a000000>
         <DBRow f0902e7481000000000000000000f03fb0cfaa9f370fca017790ac480100000001000000639793039096980012c9c9010b0000008302ff7f5a000000>
         <DBRow 00a8b10a87000000000000000000f03fe0277593410fca01bd61ad480200000001000000169093039096980015c9c9010e0000008302ff7f5a>
         <DBRow 00a8b10a87000000000000000000004000cbd3a70010ca0134c5bf480200000001000000169093039096980015c9c9010e0000008302ff7f5a000000>
         <DBRow 001882ba7d000000000000000000f03fb0c2eda85110ca01d44dc5480100000001000000149b930390969800f2c8c901000000008302ff7f5a>
         <DBRow f01373d17a000000000000000000f03fe0ea9be87910ca014d90c9480100000001000000fe95930390969800e1c8c901000000008302ff7f1e000000>
         <DBRow 50a3b10a87000000000000000000f03fb0dae8bfa410ca013d22cf480200000001000000169093039096980015c9c901000000008302ff7f5a000000>
         <DBRow 50a3b10a870000000000000000000040b0d4aadeab10ca01a8d9cf4802000000010000002296930390969800f9c8c901000000008302ff7f5a000000>
         <DBRecords>
         (
           <STuple>
           (
             <STuple>
             (
               <SStreamIdent 2>
             )
             <SDict>
             (
               <SStreamIdent 1>
               <SMarker ID: 36 >
               <STuple>
               (
                 <SMarker ID: -117 >
                 <SMarker ID: -95 >
                 <SMarker ID: 74 >
                 <SMarker ID: -116 >
                 <SMarker ID: -118 >
                 <SMarker ID: -96 >
                 <SMarker ID: -119 >
                 <SMarker ID: 116 >
                 <SMarker ID: -125 >
                 <SMarker ID: 126 >
                 <SMarker ID: -101 >
                 <SMarker ID: -115 >
                 <SMarker ID: -106 >
                 <SMarker ID: 41 >
               )
               <SStreamIdent 3>
             )
           )
         )
         <DBRow 005c3e736a0000000000000000001440d062bb918efdc9016f29f7450500000001000000bb96930390969800d8c8c90100000000830228005a0001>
         <DBRow 9cbe2f2000000000000000000000f03ff0eb1ad2fefdc9017c43fc460100000001000000c397930390969800d8c8c901000000008302ff7f5a000100>
         <DBRow 0427f5536d000000000000000000f03fb0cbb36f250bca015048424801000000010000000196930390969800e0c8c90100000000830203005a000100>
         <DBRow 9cd50e2000000000000000000000f03f7023fa4b21dac9010b816c4301000000010000003196930390969800fdc8c901000000008302ff7f5a000100>
         <DBRow 00a82d336f000000000000000000004030551585dc0fca01f7a5314805000000010000003196930390969800fdc8c9010000000083020a005a0001>
         <DBRow 4068fe3f6e0000000000000000001c4060feb17c410bca01a402a9470a000000010000002e9693039096980001c9c90100000000830214001e000100>
         <DBRow 00ba95b96e000000000000000000f03f30366bc52f0eca01711940480100000001000000919693039096980011c9c90100000000830204005a0001>
         <DBRow e0067fe0680000000000000000001040302ebdaeedf4c901a9d6f0440400000001000000609793039096980012c9c90100000000830205005a000100>
         <DBRow c84cb55b6b000000000000000000f03f408f5a9adb02ca0121208a460100000001000000609793039096980012c9c90100000000830205005a000100>
         <DBRow b085fde068000000000000000000f03ff056816f43fac9016eb19e4601000000010000006c9793039096980014c9c90100000000830205005a000100>
         <DBRow 801bf4266c000000000000000000004090cd97f0cf05ca019d7ead470200000001000000169093039096980015c9c90100000000830203005a000100>
         <DBRow 40fa51b96e000000000000000000004010707d136b0dca01d021a0460300000001000000e69593039096980023c9c90100000000830214005a000100>
         <DBRow 001882ba7d000000000000000000f03f1026ef856e10ca01bb37c8480100000001000000fd93930390969800f3c8c901000000008302ffff5a0001>
         <DBRow 00a446167200000000000000000000408024d1608e10ca01044fcc480200000001000000e293930390969800e0c8c901000000008302ffff070001>
       )
       <SLongLong '128934085416010580'>
     )
   )

So the magic 0x2A encoding in the cache files had me stumped for several days. I could see some of the data, but the packing was… odd (and no real price ever materialized out of it, turns out its a 64 bit integer, with lots of 0s ). The real problem was the zeros, or the lack of them. Turns out the packing algorithm appears to be optimized to simply not encode zero bytes, slightly reducing space. I believe that the first byte (and every “code” byte thereafter), which is split into two nibbles for this algorithm, contains a count of zeros and not zeros (bytes it simply copies to the output stream). This appears to be exclusive – either 0 is inserted or bytes are copied (per nibble), but not both.

I can’t fully verify this as I don’t have any “unpacked” in the same format, but by unpacking I can now locate more relevant data fields. Yay!

Progress is good. The parser doesn’t yet understand type 0x2A yet, but it will soon…

The parser library is a plain-vanilla C++ library, cross platform and embeddable in just about anything. I’m mainly focused on building an AST of the cache file format at this point. We can walk the AST and fetch the needed data later, which is the “easy part.” This is not a “find-magic-byte sequence and use fixed offsets” type parser

You can track progress at gitorious.org/libevecache.


Parse exception Can't identify type 0x2a at position 0x124
Beginning dump...
{Length: 3} <SInt '738197504'> <STuple>
( {Length: 4} <SMarker ID: -120 > <SIdent 'GetOrders'> <SInt '10000016'> <SInt '642'> )
<SDict>
( {Length: 1} <SObject>
( {Length: 2} <SIdent 'objectCaching.CachedMethodCallResult'> <STuple>
( {Length: 2} <SDict>
( {Length: 4} <STuple>
( {Length: 3} <SIdent '1 minute'> <NONE> <NONE> )
<SIdent 'versionCheck'> <SMarker ID: -114 > <SIdent 'sessionInfo'> )
<SSubstream>
( {Length: 3} <SLongLong '2678554370227830784'> <SString 'dbutil.RowList'> <SDict>
( {Length: 4} <SDBHeader>
( {Length: 1} <STuple>
( {Length: 2} <SString 'blue.DBRowDescriptor'> <STuple>
( {Length: 1} <STuple>
( {Length: e} <STuple>
( {Length: 2} <SMarker ID: -117 > <SInt '6'> )
<STuple>
( {Length: 2} <SMarker ID: -95 > <SInt '5'> )
<STuple>
( {Length: 2} <SMarker ID: 74 > <SInt '2'> )
<STuple>
( {Length: 2} <SMarker ID: -116 > <SInt '2'> )
<STuple>
( {Length: 2} <SMarker ID: -118 > <SInt '3'> )
<STuple>
( {Length: 2} <SMarker ID: -96 > <SInt '3'> )
<STuple>
( {Length: 2} <SMarker ID: -119 > <SInt '3'> )
<STuple>
( {Length: 2} <SMarker ID: 116 > <SInt '11'> )
<STuple>
( {Length: 2} <SMarker ID: -125 > <SInt '64'> )
<STuple>
( {Length: 2} <SMarker ID: 126 > <SInt '2'> )
<STuple>
( {Length: 2} <SMarker ID: -101 > <SInt '3'> )
<STuple>
( {Length: 2} <SMarker ID: -115 > <SInt '3'> )
<STuple>
( {Length: 2} <SMarker ID: -106 > <SInt '3'> )
<STuple>
( {Length: 2} <SMarker ID: 41 > <SInt '3'> )
)
)
)
)
<SMarker ID: 36 > <STuple>
( {Length: e} <SMarker ID: -117 > <SMarker ID: -95 > <SMarker ID: 74 > <SMarker ID: -116 > <SMarker ID: -118 > <SMarker ID: -96 > <SMarker ID: -119 > <SMarker ID: 116 > <SMarker ID: -125 > <SMarker ID: 126 > <SMarker ID: -101 > <SMarker ID: -115 > <SMarker ID: -106 > <SMarker ID: 41 > )
<SIdent 'columns'> )
)
)
)
)


The FSF has said no thanks to the .Net community promise. Not surprising in the least, and their points are all good. As I’ve said before, the promise is worth only the paper it is written on – it has no legal implications. Microsoft likes sinking their partners (see: Spyglass), and would likely continue to do so.

Speculations?

Good news everybody!

LLVM, everyone’s favorite next generation compiler architecture, now has a MSP430 backend.

The bad news? It doesn’t really work yet. Its time to dust off my compiler skills and take a prod at it.

More information:

Thread on llvm-devel.

Zed Shaw has posted a well written discussion of why he uses the GPL series of licenses.

I have to say I agree with his reasoning on all counts. I have licensed software under the BSD or MIT series of licenses in the past, but often for small little utilities that I don’t think contain much intellectual worth or don’t represent new concepts or major time investments. Anything “big” comes under the GPL.

This is a good point to discuss the applicability of the Affero GPL license. If you are developing software which will likely never offered or downloaded to a client machine (the “distribution” step in the GPL, which is absent in most web applications and SaaS), but would like to force users to offer the modified source code to your product, this is the license to use. There are very few pieces of software which carry the AGPL license to date, however with the growing trend of cloud computing, it is well worth considering.

The only downside to the AGPL are libraries, which carry the full force of the GPL license. There is no “ALGPL” version, allowing linking of code into other products without bringing the requirements of the GPL with it.

Looks like our friends at Microsoft have come up with a Community Promise governing the core of the C# and CLI architecture.

Here is the text of Microsoft’s announcement:

I have some good news to announce: Microsoft will be applying the Community Promise to the ECMA 334 and ECMA 335 specs.

ECMA 334 specifies the form and establishes the interpretation of programs written in the C# programming language, while the ECMA 335 standard defines the Common Language Infrastructure (CLI) in which applications written in multiple high-level languages can be executed in different system environments without the need to rewrite those applications to take into consideration the unique characteristics of those environments.

“The Community Promise is an excellent vehicle and, in this situation, ensures the best balance of interoperability and flexibility for developers,” Scott Guthrie, the Corporate Vice President for the .Net Developer Platform, told me July 6.

It is important to note that, under the Community Promise, anyone can freely implement these specifications with their technology, code, and solutions.

You do not need to sign a license agreement, or otherwise communicate to Microsoft how you will implement the specifications.

The Promise applies to developers, distributors, and users of Covered Implementations without regard to the development model that created the implementations, the type of copyright licenses under which it is distributed, or the associated business model.

Under the Community Promise, Microsoft provides assurance that it will not assert its Necessary Claims against anyone who makes, uses, sells, offers for sale, imports, or distributes any Covered Implementation under any type of development or distribution model, including open-source licensing models such as the LGPL or GPL.

You can find the terms of the Microsoft Community Promise here.

I told you this was good news!

Of course this isn’t a legal document by any means. But if you take it for what its worth, its a decent step forward. The problem with .Net and this agreement however is that it doesn’t cross over to the vertical components of their runtime, like Windows.Forms and ASP.NET. So I guess you can feel free to write free and open source code while using the Mono libraries which are not re-implementations of the Windows counterparts (like Gtk#)

You can read more about this on Miguel de Icaza’s blog here.

More of the beginning of the end for Java?

Check out this OLED keyswitch NKK.

Full color 64×32 display, with a SPI interface, which is much easier to use than previous products (such as the ScreenKeys)

IS15DSBFP4RGB on Mouser

As a statistic for the internet, I would like to report that my Apple Mini DisplayPort to Dual-Link DVI Adapter works just fine. I purchased it from new stock at an Apple store on April 2nd, and am using it with a 2009 Mac Mini base model (+ putty knife upgraded RAM). The monitor is an NEC LCD3090WQXi, running happily at 2560×1600.

Which brings up two main complaints:

I know this is an active adapter, with a full DisplayPort to DVI protocol converter (and high bandwidth DVI for that matter). But why is it $99? That is 1/6th of the value of a new Mini.

And why does the new Mini still ship with the same gargantuan power brick that the original Mini shipped with? Its nearly 1/3rd the size of the computer! I know Apple has worked hard to miniaturize power adapters – every other adapter is much smaller! Even the Time Capsule has a built-in power supply…