Shed Floof by the Fire, Pawprints in the Snow

My code—or rather my bugs, you could say—have apparently been trying to make an artistic statement.

No comment, except... I think they succeeded. o..o

See also, visuals.

template<> struct promote<byte, unsigned shirt> { ... }

Hmm, might be enough coding for today. You know—first it's shirts, next thing it'll be volatile unsigned dryer lint. Then I'll be casting off box<short>s and long johns; and destructing Tokyo().

A purely virtual notion I'm sure, but you just can't be too careful...

I thought I'd try the Visual .NET Forms stuff in MSVC++ 2005. I hoped I could get a decent GUI up and keep the rest of my code as clean, platform-independent C++.

Maybe I'm just stupid, but this is the simplest way I could find to get a std::wstring path out of an explorer icon dragged atop the form:

System::Void MainWin_DragDrop(
    System::Object^ sender,
    System::Windows::Forms::DragEventArgs^ e
) {
    array<String^>^ dropList =
        dynamic_cast<array<String^>^>(
            e->Data->GetData( DataFormats::FileDrop ));
    
    String^         filePathCLR = dropList[0];
    std::wstring    filePathSTL;
    	 
    // "Obvious" method
    //for each( wchar_t c in filePathCLR )
    //	filePathSTL.push_back(c);
    
    // Suggested method (MSVC documentation... srsly)
    using namespace Runtime::InteropServices;
    const wchar_t* filePathRaw = (wchar_t*)(
        (Marshal::StringToHGlobalUni( filePathCLR )).ToPointer()
    );
    filePathSTL = filePathRaw;
    Marshal::FreeHGlobal(IntPtr( (void*)filePathRaw ));
    
    m_MyObj = new SomeDocumentObject(filePathSTL);
    // ...
}

There are several interesting things to be seen here. I'm not sure what to think of them.

For one thing, this isn't even C++! They've added a whole chunk of C# as completely new syntax. Seen here are the ^ which is their garbage-collected heap pointer, array (which is a keyword and derives from System::Array), and a few bits of their class library. Also notice the for each, where each and in are context-sensitive (!!) as keywords.

Oh, and don't even get me started on the freaking casts.

This syntax is completely required. The form designer generates it, and their library depends on the special references. That's because if you compile in "safe" mode, hoping to run under someone's tight security policy (and they encourage you to)... pointers aren't even allowed!

Naturally, this breaks just about every useful piece of C and C++ out there, including the all-important STL which sets C++ apart. While I understand the security motivation, I think this is misleading on MS's part, since at that point, it's not C++ anymore! It's just another dialect of C#, or maybe C# with templates. :/

I could simply compile in "pure" mode (effectively, insecure bytecode), and use the STL with the bureaucracy above, but it's still annoying. Mmmfeh.

So DietPower, the food logger I use, decided as long as I'm sitting here, I could wait two minutes for the food log to open. It was already slow, but now it's firmly in the realm of code that doesn't scale.

C'mon, it's clearly a C job. No excuse. I know people who write faster apps in Perl!

Another irritating thing is it's missing an export option, so the only way to get the logs out involves manual inspection, and then writing the code. The latter's not so hard, but I always used to cringe at binary files. Maybe the braver people would drag out a hex editor.

Well, the first thing I reach for is EDIT.COM. That used to be because it's all I had that reliably saved binaries... too bad it doesn't do hex, right? But after awhile I noticed that an ascii view is really useful, quite possibly moreso.

For one, you get the best use of screen space, which reveals a lot of patterns. Intel code is very dense, with the occasional word-size data thrown in. C structs with small numbers (e.g. most of them) leave a lot of zero padding. Pointers and offsets can be seen growing throughout the file. Text, of course, is immediately readable.

Repeated data shows up especially well, since nearly every byte has a unique glyph. The exceptions, 0x00/0x20/0xff, are blank. Happily, this includes various representations of nil: space, the integers 0 and -1, floating-point zero--and unused numeric precision.

Other values show up too, for example values centered around 0x3f (?, @, A) which are sign/exponent bits for small positive floats. "  Ç┐" happens to be 0xbf800000, or -1.0. At left, it marks unspecified nutritional values. (Sloppy coding has introduced other negative values as well!)

If the file is just a series of structs, it shows up as angular striations, betraying the length and number of the records. Usually somewhere nearby is the count. If you know your hex and ascii (essentially base-16/256), you'll quickly find it, and now you can write a skeletal reader.

And then you can go try all the program's special cases, and make note of what it spits out. This is how I wrote my OpenCanvas reader. Maybe I can get DietPower's logs into a spreadsheet or something...

It does give me thoughts, though. Using EDIT works great, but it's still a pain to do the math. I wonder if there's a better editor out there. I think I should be able to select regions, say "this looks like a record", and have the thing pattern-matched down the whole file. Then I could say "these are float fields", and it would update everywhere.

I think I would have circular tooltips, where you hover over some data and it shows you all the different values it could be in each representation it knows, and then the most likely one. (0's or 1's on the left = small int, high bits near 0xbf, 0x3f = small float, compare to values in other instances of the record...) Then you'd right-drag through a pie menu to choose one of them.

There could even be a hex view, either through a lens tool, or using a color mapping on top of the numbers, to show patterns. Or you could space things out and display assembler inline with all the other data, using heuristics (statistics, file headers) or manual selection to identify the code.

Ideally it would come with different plugins for the known formats, and people could write their own. You could use it as a teaching tool for Operating systems 101, or to help debug things, or repair corrupt files.

Ohwell, I'm probably dreaming. But it would be helpful right now.

Some months ago I found a couple of brilliant pages (1, 2) on dealing with graphics data. By which I mean, four-component vectors packed into machine words. E.g. 0xAARRGGBB or struct { uint8_t r, g, b, a; }.

Applications like Photoshop or OC, are really just a slick interface over all these vectors. Since there are naturally quite a lot (e.g. tens of megabytes) of them, the authors have invested quite a lot of effort to speed up the math.

This is the lovely part. You don't have to know calculus, but you do need a twisted mind. For example, these two snippets add and subtract vectors, limiting the results to byte range. So annoying to do componentwise, but look!

sum = x + y; low_bits = (x ^ y) & 0x010101; carries = (sum - low_bits) & 0x01010100; modulo = sum - carries; clamp = carries - (carries >> 8); result = modulo | clamp; (modified, the original page did 16 bits)

diff = (x - y) + 0x01010100; low_bits = (x ^ y) & 0x01010100; borrows = (diff - low_bits) & 0x01010100; modulo = diff - borrows; clamp = borrows - (borrows >> 8); result = modulo & clamp;

They compile to 12..14 intel instructions, adding in parallel and saving up to three expensive branches. Some manual assembler can even fix the carry problem (on the add) and do the full vector.

Here's a premultiplied alpha blend, resembling code from the linked page. They are computing dest_C = dest_C*(255-src_A)/255 + src_C. The first is approximate, and the second (in a not so obvious way) exact:

dest_ag = (dest & 0xff00ff00) >> 8; dest_rb = dest & 0x00ff00ff; alpha = 0x100 - (src >> 24); dest_ag *= alpha; dest_rb *= alpha; dest_ag = dest_ag & 0xff00ff00; dest_rb = (dest_rb >> 8) & 0x00ff00ff; dest = dest_ag + dest_rb + src;

dest_ag = (dest & 0xff00ff00) >> 8; dest_rb = dest & 0x00ff00ff; alpha = 0xff - (src >> 24); dest_ag = alpha * dest_ag + 0x00800080; dest_rb = alpha * dest_rb + 0x00800080; dest_ag = ((dest_ag >> 8) & 0x00ff00ff) + dest_ag; dest_rb = ((dest_rb >> 8) & 0x00ff00ff) + dest_rb; dest_ag = dest_ag & 0xff00ff00; dest_rb = (dest_rb >> 8) & 0x00ff00ff; dest = dest_ag + dest_rb + src;

This is based on the principle that 4 * 1020304 = 4 * (1000000 + 20000 + 300 + 4) = 4081216. The coefficient multiplies digits independently, preserving their place values. So while it looks complicated, it saves two multiplies and (in the second case) four (!) divides. The remaining logic is easily parallelized on its own, a cinch for modern compilers and CPUs.

Finally, here's one I noticed! It's just a componentwise product, treating the bytes as unit fractions:

dest_ag = (dest & 0xff00ff00) >> 8; dest_rb = dest & 0x00ff00ff; src_ag = (src & 0xff00ff00) >> 8; src_rb = src & 0x00ff00ff; dest_ag *= src_ag + 0x00010001; dest_rb *= src_rb + 0x00010001; dest_ag = (dest_ag >> 16 & 0xff000000) + (dest_ag & 0x0000ff00); dest_rb = (dest_rb >> 24 & 0x00ff0000) + (dest_rb >> 8 & 0x000000ff); dest = dest_ag + dest_rb;

This one's approximate, and needs a 32x32->64bit multiply (usually an inline library function or some assembler). Though 0*0 = 0, and 255*255 = 255, as intended. It's actually not so obvious why this works. The short story is that it's based on the expansion of (a + b)(x + y)...

(2¹⁶*b + a) * (2¹⁶*y + x) = 2³²*b*y + 2¹⁶*(b*x + a*y) + a*x

( explanation )

G'dammit... OpenCanvas' networking has taken to taunting me. Some 30-60 minutes in it'll just stop reading data from everyone else, so I'm effectively bumped out of the session, even though it's receiving it. Naturally this happens as soon as I really get into it.

So, I guess there's my motivation. I want a replacement, and I know roughly how I want it to work. I'll prolly try and think on the class design for a few days. I've been flailing way too much with microscopic C++ issues, so maybe the trip will be an opportunity to step back from the compiler, and work out something minimal and reasonable on paper. (I honestly don't think anything on the level of OC should be more than 3-5,000 lines of code.)

Wait, Tala, trip you say? What trip? Gah. Some relatives from the east coast are having a wedding up in Delaware, and we were all invited. It's a fifteen-hour drive. Yeeeesh. Since past the first day we will probably be bored beyond belief, we're doing a day of driving each way, and a day at the wedding. So I leave in 3-4 hours (x..x!) and get back on my birthday, e.g. Sunday. Double-yeeesh!

Honestly I'm tempted both ways... it would be a peaceful relaxing weekend at home with the parents gone, but I need to get out too. Total tradeoff. For better or worse, I haven't seen these people in years. That will be nicely awkward. Wheeee.

So, I'll see you all in a few days.

Second Life, the sprawling hack that it is, has me thinking about multiuser systems lately, particularly how to do them better. One really cool thing would be to have peer-to-peer spaces. For a small group, that would be a huge improvement over the $200/mo Lindens want to maintain an island. Just connect to your local tracker, ala BT, and have all the room your slowest clients can cope with. It goes away when the last person leaves, or someone could save to disk. What could be simpler?

Well assuming you tackled the voluntary coherence issues, there is still no authority involved. It's peer-to-peer, so how could there be? Kinna confusing. ( Let me outline the situation... )

Now suppose our ever-enterprising Carol hacks apart her VM. The first thing she does is add an instruction to let her see all the objects and their data, particularly those in S_w. Then she uses that to inspect Bob's bank account, and is sorely disappointed because Bob is fresh out of funds. So she builds a camera situated in S_a, that lets her peek right into Alice and Bob's skybox. (Which, we suppose, is what he spent the money on—it is peppered with luxurious textures and neon poseballs. She makes a note to copy her favorites.)

I think it's very important to point out here that, while nobody can violate security (e.g. forge object pointers) inside the VM, with contemporary hardware it will always be possible to hack the OS, machine, security chips, etc etc... and therefore, data extraction is a problem. SL does in fact have the same issues, but LL has been hushed about it. Probably because people never seem to understand this, and love to get upset over it... but really, it's a big fat social problem IMHO, considering what little current tech can do against a very determined Carol.

The solution I think is to use a whitelist (challenge-response), and not to have your skybox, or your banking, in public space (plain sight). Just RL common sense, there. But, but, I'm really getting off track here. The problem I wanted to talk about, and solve, is something different and much worse than peeping toms.

So while I was rambling, Carol has advanced her plans for S_w domination. Now she wants to abuse Alice and Bob's blissfully consistent view of the world. To do this requires no cracking whatsoever—just abuse of the protocol. All she needs to do is send two different messages or responses to Alice and Bob's S_w. The two copies will then slowly desync as the code takes different paths on each side. Obviously this is going to break, but to fix it, we need to know how.

( Somewhere along the line, Alice is going to try and effect the inconsistent world... Bob goes "LOLWTF!" )

Which points to a partial solution. What if we could make this situation arbitrarily likely (e.g. extremely likely) to happen with the smallest perturbation? Then we could roll back an arbitrarily short time to the past (requiring arbitrarily little RAM to store the difference), and nobody loses much work. It would also force Carol to run the exact same data and code, or else be found out, even if she runs a second cracked copy for herself.

Essentially, what I'm proposing, is the Halting Problem put to practical use. Message consistency proves with high probability that you ran the same code.

( The garbageman knows what you ate for dinner )

This would probably be integrated into some sort of "heartbeat" as a way to keep everyone sync'd within some bounded time. Note that it's also symmetrical. If Alice were to deliberately screw up her hash, Bob might think -she- strayed, and vice versa. To this point, any "accusation" is private. What to do if several peers disagree? Start voting people off the island? (Heheh, sorry. ^..^;)

The thing with voting is that it's only good if you play with several friends, or at least neutrals. But you don't want to play with cheaters anyway, I presume. At the least, you would discover something was up and take your toys elsewhere. The real problem, is if a large gang snuck up on your friends, and all of a sudden, voted you out. Sort of a DDoS... unless maybe you deliberately trusted your friends? Sticky issue.

Hrrrrmm. It's interesting to think about anyways. Let me know what I forgot. n..n

So some time ago, Microsoft came up with a nice new OO graphics API known as GDI+. While basic, it's a great first step and has essential things like transparency, antialiasing, gradients, image loaders, and a crapload of ways to shuffle data around without excess fussing (GDI+ on a DirectDraw surface? Sure!). It's just generally so much cleaner. There's no more confusing handle selection, and in C++ you can just have local objects on the stack. Very neat.

So naturally I spent a few hours playing around. To my great horror, I find:
1) This is a software engine (no acceleration like the crufty old GDI has).
2) It's doing a bitmap copy or two for, e.g. every DrawLine thrown at the screen!
3) I can watch this happen!!*
4) Resizing the window is slower--recreating Bitmap and Graphics objects incurs visible delays!?

Bwauuuugh! Okay, I get why the compositing is molasses, it's a read/write op, which quickly goes to Video Hell. But I turned that off and it still hardly qualifies as fast.**

Double-buffering, of course, fixes it. For the most part. If my bitmap format matches the screen. But thing is, most office-type apps don't need double-buffering. What they need is fast lines, boxes, text and scrolling (aka big, fast video-side copies)... all inside a fullscreen window, worst-case. Buffering doesn't provide that; AGP is barely fast enough without two or three layers of abstraction in the way. IMHO, that's the biggest reason Java and other "modern" apps feel so slow. If you're running a PCI-E board I bet it's great, but for me, it just lacks the crisp response I associate with native code.

Yeah, yeah, I know... some will say, what's he spewing about, he should buy new hardware! To which I reply, mine works fine, it doesn't need to be in a landfill, and by the way, would they like to donate? :P Ah hell, I really am rambling now. G'nightxx0rs y'all.

* Cue nostalgia regarding my QBASIC days, which has, I realise, now faded. SCREEN 13, baby!
** CompositingModeSourceCopy also disablesneuters antialiasing. And I'm using a Delphi wrapper, not C++. Maybe I'm doing something wrong, I dunno. But clearly DrawLine et al is not CPU-bound, it's just the copies. Google suggests others are running into this too. :(

Anyone remember that crazyass robot in Mario Paint? The thing that held a single measly slot and took a couple minutes just to fecking save?

Well apparently Mario Paint has 32KBytes of saveram on the cart. When I read this I was skeptical... Hmm, I thought, that's enough for one screen, but what about the rest? Well let's find out!

2 * 248x168 pixels * 4/8 bytes/pixel (16 colors) (drawing and animation areas, = 41664 bytes)
+ 256 * 2 (x,y) (animation path = 512 bytes)
+ 16 * 16x16 pixels * 4/8 bytes/pixel (stamps, = 2048 bytes)
+ 96 bars * 3 notes (music, = 288 bytes)
= at least 44512 bytes or 43.5KB

Okay fine, the SNES comes with 128KB of memory built-in. Tons of room for even lavish auxiliary buffers. However, 44KB is almost half again the size of the saveram. What you say!! Well they must be compressing it. Oh ho hooohhh... this gives me evil ideass...

Those of you who tried to be smartarses and .zip your .jpg files (or worse your .zip files :D) before you realised what happened, will see what's coming. No "compression" tool can shrink everything, because if it could, you'd just .zip your .zips until they disappeared into nothing! And then upload your nothing in infinitesimal time! As cool as that would be, the fact is that some data will not shrink, in fact some of it will expand. Namely, the "densest" data, with the fewest patterns (like, say, your .zip files). Data like the canvas to the right.

So for this to work, Nintendo (bless their skimping hearts) need to shrink everything to about 70% of the original size... a reasonable margin. Given the sloooow speed, they are probably using LZW or somesuch—not a favorite of their 3Mhz CPU, but something respectable that will get the job done, and crunch all the simple kiddie drawings, and even then most anything worth saving. But look what happens when you airbrush the whole canvas! Ahahahaaah! Yes, the robot explodes! They even included a helpful message and a little animation. This SO just made my day! ^..^;