MiscellaneouZ

New venture - Android decompiler

2012-11-26T18:37:00.000+01:00

I'm currently working on JEB, an interactive Android app decompiler for security analysts and reverse engineers.

JEB should be out late December/early Jan. Check out www.android-decompiler.com to get all the details.

Visualizing lemniscates and Cassinian curves

2011-11-28T00:08:00.001+01:00

Last night was fun. I found a USB stick I haven't used in years and couldn’t resist browsing its content. My excitement rose when I retrieved - among various other juicy and less juicy pieces of data, mostly dating back from the college era – an archive containing many old C programs. I stumbled upon this piece of code /rambling_begins I wrote at a time my friends and I were venerating Brian Greene et al. and our bible was the Elegant Universe. Eventually, my friends went to study physics but did not major in cosmology. Applied physics pay the bills. String theory physicists are starving to death nowadays! /rambling_over.

So the idea was to visually represent lemniscates.

Lemniscates and its derivatives are fascinating mathematical objects. (Their construction was appealing because it resembled the ellipse's.)

Remember that an ellipse is defined by its two centers C0, C1 and the set of points P such that dist(C0,P)+dist(C1,P) is constant:

Image (c) Wikipedia

A lemniscate is also defined by its two centers C0, C1 and a set of points P, but this time d=dist(C0,P)*dist(C1,P) must be constant. The most famous lemniscate is Bernouilli’s, where d is set to sqrt(dist(C0,C1)/2). This produces … the infinite sign:

Image (c) Mathcurve.com

Generalized, these lemniscates are formally called Cassini’s ovals, and we can intuitively guess that greater values of d generate what look like ellipses, whereas smaller values of d generate pairs of pseudo-circles:

Image (c) Mathcurve.com

Now the last step was to generalize that to 3, 4 and more centers. The formal name of these beauties is Cassinian curves, and they look like that:

Image (c) Mathcurve.com

Back in the days, I didn’t know these objects had real names – not to mention their use in electrostatic fields analysis. I was experimenting and simply called them generalized lemnicates. Anyway, below are a few of screenshots with 2 centers, 3 centers, 6 centers, and a couple of zoomed-in areas.

The trick to get these cool gradients is to rely on the RGB implementation used by most programming frameworks. The (Red, Green, Blue) tuple is represented by 3 bytes stored in a 32-bit dword. (The high-byte can be the alpha channel, but is irrelevant in the case of raw colors.) If we define d=dist(C0,P)*dist(C1,P)*…*dist(Cn,P) and represent d as a colored pixel whose RGB value is directly proportional to d (ie, a number between 0 and 0FFFFFFh).

The yellow-ish separations mean that the Blue byte is about to be incremented. Of course, this depends on the number of centers and how close they are to each other: these initial conditions yield the range of value d can have within the window. With more 10 centers, very close to each other, it takes a while to get to Blue=1, therefore we can see increments of Green (at least the first 4 are clearly marked out).

I’ve attached the source and binary so you can experiment yourself. (Sorry for the Linux folks out there, it’s Windows C…)

Raasta

2011-11-03T03:47:00.008+01:00

I haven't posted in a very long while, mainly due to time and professional constraints. This will be fixed eventually.

Meanwhile, this atypical post is meant to let my (many, many) readers know that I recently released my first Android app: Raasta is a powerful, battery-friendly GPS tracker designed to fully operate in areas without data reception. You can record your progress and geolocate yourself during hikes, roadtrips or explorations. It's packed with features, including editable landmarks, custom GPS periods, KML exports, GMap overlay, etc.

Check out the full description and download the app here: https://market.android.com/details?id=com.pnfsoftware.raasta

Best of all: it's entirely free!

Edit: Also, I've decided to join the Twitter crowd. You can follow me @NicolasFalliere. Not a lot of tweets at the moment, I'm still in the discovery phase :)

Windows 7 and XP SP3 system call tables

2010-01-19T22:00:00.003+01:00

A short post to let you know that I've uploaded system call tables for Windows Seven SP0 and Windows XP SP3 here:

The Python and C versions can easily be integrated into projects.

The old tables (NT, 2K, XP, etc.) were generated based on the MetaSploit System Call Tables page, so thanks to them for that.

Edit: here's a diff with Vista SP0 (a diff with SP2 would be more valuable, will do eventually):

Syscalls added:

NtAllocateReserveObject
NtAlpcRevokeSecurityContext
NtCreateKeyTransacted
NtCreateProfileEx
NtCreateUserProcess
NtDisableLastKnownGood
NtDrawText
NtEnableLastKnownGood
NtEnumerateTransactionObject
NtNotifyChangeSession
NtOpenKeyEx
NtOpenKeyTransacted
NtOpenKeyTransactedEx
NtQuerySecurityAttributesToken
NtQuerySystemInformationEx
NtQueueApcThreadEx
NtReplacePartitionUnit
NtSerializeBoot
NtSetIoCompletionEx
NtSetTimerEx
NtUmsThreadYield

Syscalls removed:

NtPullTransaction
NtGetMUILicenseInfo
NtClearMUILicenseInfo
NtRequestWakeupLatency
NtRollbackSavepointTransaction
NtClearAllSavepointsTransaction
NtClearSavepointTransaction
NtRequestDeviceWakeup
NtSavepointComplete
NtStartTm
NtCancelDeviceWakeupRequest
NtMarshallTransaction
NtListTransactions
NtSavepointTransaction

Seems like there's plenty to investigate (NtCreateUserProcess, NtSerializeBoot, NtReplacePartitionUnit, NtQuerySystemInformationEx, NtQueueApcThreadEx, ...).

MmGetPhysicalAddress implementation tricks

2010-01-10T12:34:00.000+01:00

MmGetPhysicalAddress is a kernel-exported API that allows converting a virtual address to a physical one.

Quick reminder: Windows runs in protected (or long/IA64) mode with paging enabled, plus/minus physical address extensions enabled. The post focus on a 32-bit kernel with PAE disabled for enhanced clarity.

The PDE/PTE structures for 4Kb pages are (from Intel manual):

The PDE structure for 4Mb pages is:

The conversion to a physical address is done internally by the hardware. No instruction implements a physical-to-virtual address conversion. When the operating system uses paging, the key to physical conversion lies in CR3. This register contains the physical address to the page-directory entries table.

In order to do a virtual-to-physical converion programmatically, one needs to know where the page translation tables are located in virtual memory. When created, these pages are referenced only by their physical addresses, stored in the page-directory or page-table entries (see pictures above). This chicken&egg problem is solved by Windows (and most likely other x86 OSs) by reserving a range in the kernel address space for all lowest-level page-description pages (PTEs for 4Kb pages, PDEs for 4Mb pages).

Let's examine how MmGetPhysicalAddress is implemented in the simplest version of a Windows XP SP3 kernel (32-bit, PAE disabled):

.text:0042E046 ; unsigned __int64 __stdcall MmGetPhysicalAddress(unsigned int BaseAddress)
.text:0042E046
.text:0042E046 BaseAddress     = dword ptr  8
.text:0042E046
.text:0042E046                 mov     edi, edi
.text:0042E048                 push    ebp
.text:0042E049                 mov     ebp, esp
.text:0042E04B                 push    esi
.text:0042E04C                 mov     esi, [ebp+BaseAddress]
.text:0042E04F                 mov     eax, esi
.text:0042E051                 shr     eax, 14h
.text:0042E054                 and     eax, 0FFCh
.text:0042E059                 mov     ecx, [eax-3FD00000h]
.text:0042E05F                 mov     eax, ecx
.text:0042E061                 and     ax, 81h
.text:0042E065                 cmp     al, 81h ;present? page size?
.text:0042E067                 jnz     short 4Kbpage
.text:0042E067
.text:0042E069                 mov     eax, esi ;4Mb page
.text:0042E06B                 shr     eax, 0Ch
.text:0042E06E                 and     eax, 3FFh
.text:0042E073                 shr     ecx, 0Ch
.text:0042E076                 add     eax, ecx
.text:0042E076
.text:0042E078
.text:0042E078 convert:
.text:0042E078                 xor     ecx, ecx
.text:0042E07A                 shld    ecx, eax, 0Ch
.text:0042E07E                 shl     eax, 0Ch
.text:0042E081                 and     esi, 0FFFh
.text:0042E087                 add     eax, esi
.text:0042E089                 mov     edx, ecx ;0
.text:0042E089
.text:0042E08B
.text:0042E08B done:
.text:0042E08B                 pop     esi
.text:0042E08C                 pop     ebp
.text:0042E08D                 retn    4
.text:0042E090
.text:0042E090 4Kbpage:
.text:0042E090                 test    cl, 1 ;present?
.text:0042E093                 jz      short error
.text:0042E093
.text:0042E095                 mov     eax, esi
.text:0042E097                 shr     eax, 0Ah
.text:0042E09A                 and     eax, 3FFFFCh
.text:0042E09F                 sub     eax, 40000000h
.text:0042E0A4                 mov     eax, [eax]
.text:0042E0A6                 test    al, 1 ;PTE present?
.text:0042E0A8                 jz      short error
.text:0042E0A8
.text:0042E0AA                 shr     eax, 0Ch
.text:0042E0AD                 jmp     short convert
.text:0042E0AF
.text:0042E0AF error:
.text:0042E0AF                 xor     eax, eax
.text:0042E0B1                 xor     edx, edx
.text:0042E0B3                 jmp     short done
.text:0042E0B3
.text:0042E0B3 _MmGetPhysicalAddress@4 endp

Remember the VA is decomposed into 3 or 2 parts:
- 3 parts for 4Kb pages: [10bits=PDE index / 10bits=PTE index / 12bit=Page offset]
- 2 parts for 4Mb pages: [10bits=PDE index / 22bits=Page offset]

The code first gets the PDE index*4, which is the PDE offset relative to CR3 since PDE entries are 4-byte long. This value is added to -3FD00000. The PDE offset being in [0,FFC], the result will be in [C0300000,C0300FFC]. Now, the first PDE is pointed by CR3. Which means that physical_to_virtual(CR3)=C0300000, for all processes. The range [C0300000,C0301000[ contains the 0x400 PDEs.

A comparison then checks if the page is present or not (bit0) and the function returns 0 if the page is not present. The comparison also checks for bit7; if set, this bit indicates a 4Mb page and a different, simpler code branch is executed.

For a 4Kb PDE, the next 10 bits of the VA are extracted, then made a PTE offset in [0,FFC]. The offset is added to -40000000. The resulting value is in [C0000000, C03FFFFC]. This means the PTEs are in the range [C0000000, C0400000[. It's important to understand that this range is "reserved"; only a handful of these pages are actually mapped to physical ones, as explained below.

(The physical address is then calculated by extracting the page offset part of the VA (bottom 12 or 22 bits) and adding it to the physical address of the lowest-level page in the translation hierarchy.)

What's interesting in this scheme is the address range used. Let's consider a 3-level hierarchy (4Kb pages). CR3 "points" to C0300000, ie the first PDE is at C0300000. The PTEs go from C0000000 to C0400000: The PDE range overlaps the PTE range! And not anywhere, exactly at the 3/4th of this range; which makes sense since the 3/4th of a 32-bit address space also start at C0000000. This is not random of course: the PDEs are themselves referenced by the PTEs to allow the processor to access the [C0000000, C0400000[ range!

This may seem a bit obscure, plus my explanations here are pretty poor. It's funny how explaining 30 lines of smart assembly can be so tricky... The thing to remember to understand this is that the CPU offers NO facility to do physical to virtual conversion. But to let access the kernel access the pages that allow the CPU to do this conversion internally, they must be accessible in virtual memory. And to be accessible in virtual memory, they must be referenced by themselves. This self-reference mechanism allows the implemention of MmGetPhysicalAddress.

Quick lab experiment. Fire up WinDbg, local kernel debugging:

lkd> !process 0 0 System
PROCESS 81bcc830 SessionId: none Cid: 0004 Peb: 00000000 ParentCid: 0000
DirBase: 00039000 ObjectTable: e1000cc0 HandleCount: 244.
Image: System

DirBase is the physical address of the first PDE (loaded into CR3).
We can confirm that by check the field in the associated EPROCESS structure:

lkd> dt _EPROCESS Pcb.DirectoryTableBase 81bcc830
+0x000 Pcb :
+0x018 DirectoryTableBase : [2] 0x39000

Now, let's get the physical address of C0300000. We use !vtop, with the PFN page for the process (39000 >> 12):

lkd> !vtop 39 c0300000
Pdi 300 Pti 300
c0300000 00039000 pfn(00039)

The result is 39000, which confirms that C0300000 maps the PDEs.

You can check it for other processes, for instance WinDbg itself:

lkd> !process 0 0 windbg.exe
PROCESS 81ad8410 SessionId: 0 Cid: 049c Peb: 7ffd7000 ParentCid: 028c
DirBase: 00ae9000 ObjectTable: e1c446b0 HandleCount: 614.
Image: windbg.exe

lkd> !vtop ae9 c0300000
Pdi 300 Pti 300
c0300000 00ae9000 pfn(00ae9)

On moving register

2009-12-16T22:32:00.004+01:00

One of the great *cough* things of the IA32 architecture is that it offers multiple ways to encode identical instructions. For instance, the mov instruction is implemented by several opcodes - to support multiple variations of the instruction, for instance mov reg, [mem], mov reg, imm , etc.).
Specifically, opcode 89h (mov Ev, Gv) and opcode 8Bh (mov Gv, Ev) are used to encode mov [mem], reg and mov reg, [mem], respectively. Both are also used to encode mov reg, reg. So which one should we use?

With Microsoft dev tools (MASM, CL), opcode 8B was chosen. This means that mov ebp, esp, this classic compiler idiom used in function prologues, is implemented as 8B EC; the alternate form being 89 E5 by the way.

Yesterday, I was wondering, "Why the heck did MS decide to implement move from register to register this way in their compiler suite? Did they have some Intel guidance here? Did they flip a coin? ...". Anyways, I could not believe this choice was innocent.

I first had a quick look at Intel's optimization manual but couldn't find a hint in it - I may have missed that though.

So I decided to code a simple program to benchmark both instructions. I focused on "mov ebp, esp" since it's what initially this whole thing...


__declspec(naked) __int64 test1(void)
{
__asm
{
rdtsc
push    edx
push    eax

mov     edx, ebp
mov     eax, esp

mov     ecx, COUNT
dummy:
_emit   0x8B    // mov ebp, esp
_emit   0xEC
add     esp, 0x1234
dec     ecx
jg      dummy

mov     ebp, edx
mov     esp, eax

rdtsc
sub     eax, [esp]
sbb     edx, [esp+4]
add     esp, 8

retn
}
}

test1's counterpart, test2, is exactly the same routine except that the mov is implemented as 89 E5. I ran both of these 10 times with COUNT set to 100 millions. The output below shows the routine duration in CPU tick count for test1 (t1), test2 (t2), and the delta (t2-t1).


266427630, 239098970 -> -27328660
198251880, 236396490 -> 38144610
197485280, 236592800 -> 39107520
198359910, 240731530 -> 42371620
198169630, 236203160 -> 38033530
199283790, 237357990 -> 38074200
198334600, 238307940 -> 39973340
201726060, 237601250 -> 35875190
199196030, 235864980 -> 36668950
197668180, 236878930 -> 39210750
198189520, 236734830 -> 38545310
198769940, 236796360 -> 38026420
198463880, 236996720 -> 38532840
197608520, 235117620 -> 37509100
198994300, 237364120 -> 38369820
198324810, 238987550 -> 40662740
197842630, 236818990 -> 38976360
197126140, 236928430 -> 39802290
198637450, 237262350 -> 38624900
197569520, 235503910 -> 37934390

Omitting the first line (performance likely impacted by the CPU caching the memory area containing both routines), it appears that the first form is about 20% faster than the second. And this is not not stack-register specific as I had the same result with mov eax, edx for instance.

So, using opcode 8B for mov reg, reg seems like a good choice - in practice, I have no clue if this makes a difference during execution of a real program.

I still don't know why this choice is what it is though... if anyone (somebody who worked on a real-world C compiler for instance) has a clue, please leave a comment.

Update: I've just noticed NASM generates the alternate form 89 E5.

As for the guesswork: an assembler, to decide which opcode could be used to implement the desired instruction, can use different approach. A simple one could be to go through the opcodes in sequence (00 though FF, then 0F 00 through 0F FF, etc.), and use the first opcode encountered that fits. In this case, that would be 89. And now that I'm writing this, I realize that the simple x86 assembler I wrote in the past uses this method, and therefore should generate 89 E5 like NASM does. The fact that Microsoft tools do not makes me think it is a deliberate design decision...

Why are GDT descriptors so messed up?

2009-11-21T10:43:00.008+01:00

Ever wondered why a GDT descriptor had such a fragmented format? Like anybody born in the 80's, I have.

Here is a 64-bit, standard, non-system, generic GDT segment descriptor:

The base address is fragmented into 2 pieces (low 24 bits, high 8 bits), as is the segment limit (low 16 bits, high 8 bits). Why so?

The answer is, you guessed, backward compatibility. And the guilty is the 80286. This processor was introduced in 1982, and was the first to support Protected Mode (PM). This PM was not exactly the one we know and use nowadays though; it was simpler, sort of a version 0.1 is you will.

The 286 manual here shows us the encoding of a standard GDT descriptor - check figure 6-3. Its size is 8 bytes, but the upper 2 bytes "must be set to 0 for compatibility with iAPX 386". Interesting; so even then, they were envisaging some PM extensions... The meaningful data is contained in the low 6 bytes, formatting a non-fragmented descriptor:
- bytes 0-1: 16-bit limit
- bytes 2-4: 24-bit base
- byte 5: flags

So wait. Does it mean a segment can be at max 64Kb? And a 24-bit base means that only 16Mb of memory are physically addressable, right? - you say. Well, yes and yes. It's old-PM, remember.

The new version introduced by the 386 has its lot of improvements, among which:

Real 32-bit addressing: an extra byte for the base (8th position) was added, making it 32-bit long
The possibility to have 4Gb long segments (as opposed to 64Kb...): 4 bits were added to the limit field, making it 20 bits. Since 20 bits can only address 1Mb, 4 extra attribute bits were added, including the G bit (pos.23). Setting the G(ranularity) bit means the limit field indicates the last addressable 4-Kb block. Therefore, one sets the limit to 0xFFFFF with G=1 to have a 4Gb segment (like all modern OS do).

Which explains why GDT descriptors seem so messed up...

Another interesting bit introduced in the extra 4-bit of the attributes field is the D/B bit (pos.22). This bit indicates the default operand-size of the segment, and setting it to 1 means it's 32-bit. It was of course set to 0 for the 286 "6-byte" descriptors. Just one more element that just shows how the 386 was the real cornerstone, implementing the things that lacked in the 286 (including the paging unit), and became a standard.

If you want to know more about this, check out the Wikipedia PM history section as well as the 286 manual mentioned earlier. Also, a very interesting trivia on the 286 is how the inability to switch back from protected-mode to real-more gave a few guys at Microsoft some very hard (and fun) time!

Detecting simple hypervisors

2009-11-06T16:14:00.005+01:00

This was tested only on Intel VT-x but it might work as well with AMD-V. In between a couple of blue screens, I realized there exist many simple ways to detect primitive HVM rootkits - ie, the ones that don't implement all the code required to achieve super-stealth.

Let me give you a simple example. CPUID is a peculiar instruction; it's the only non ring-0 allowed instruction that will unconditionally trigger a VM-exit (Vol.3B:253669, p21-2). If you trace over CPUID in your favorite debugger, the VM-exit will happen: the CPU enters VMX-Root mode, and your VMM is called to handle the offending instruction.

The lazy coder would write something like:


// emulate CPUID
if(Reason == EXIT_REASON_CPUID) then
    pushad
    mov     eax, GuestEax
    mov     ecx, GuestEcx
    cpuid
    mov     GuestEax, eax
    mov     GuestEcx, ecx
    mov     GuestEdx, edx
    mov     GuestEbx, ebx
    popad
    ...

// update isntruction pointer
GuestEip += 2

vmresume()

Well, that's not enough. Execution will resume after CPUID. The trap flag will raise the debug exception after executing the instruction that follows... and there you have one simple way to detect poorly coded HVMs. One way to prevent this would be to inject a vectored event (INT1) on VM-entry.

This piece of assembly code implements the above trick (if we may call it so):


    call    GetCurrentProcess
    push    1
    push    eax
    call    SetProcessAffinityMask

    push    offset seh
    push    dword ptr fs:[0]
    mov     fs:[0], esp

    pushfd
    or      dword ptr [esp], 100h
    popfd

    cpuid

traphere:
    mov     eax, 1
    jmp     done
    
seh:
    mov     eax, [esp+0Ch]
    cmp     dword ptr [eax+0B8h], traphere
    setne   al
    movzx   eax, al

done:
    add     eax, 30h
    push    eax
    push    esp
    call    crt_printf

    push    eax
    call    ExitProcess

(On SMP systems, change the thread affinity to execute the test on other CPUs.)

There are other similar ways to detect a hypervisor from user-mode - again, assuming its implementation is lacking.

New Mebroot domains for the summer

2009-07-16T11:07:00.009+02:00

The last variant of Mebroot's driver uses an obfuscated domain generation algorithm to connect to C&C servers. Here are the domains for this summer, you might want to block them for whatever reason.

The first domain, week-based, is used first (though, after the hardcoded domain in the driver itself); the second domain is day-based and used as a failsafe. On top of '.com', the TLDs '.net' and '.biz' are tried as well.


2009/07/17: bdcxduds.com xdjxekgt.com
2009/07/18: bdcxduds.com ejswwhvk.com
2009/07/19: swuvxcds.com khkciudw.com
2009/07/20: swuvxcds.com kxhwcceu.com
2009/07/21: swuvxcds.com xhxvdsck.com
2009/07/22: swuvxcds.com hkssvihg.com
2009/07/23: swuvxcds.com jwjchkci.com
2009/07/24: swuvxcds.com vkcvuksd.com
2009/07/25: swuvxcds.com ecjhdvue.com
2009/07/26: vxvtvhik.com kvcwhwgj.com
2009/07/27: vxvtvhik.com kvbdxjhc.com
2009/07/28: vxvtvhik.com uuvksskh.com
2009/07/29: vxvtvhik.com tkevtxue.com
2009/07/30: vxvtvhik.com vdkhsccs.com
2009/07/31: vxvtvhik.com feuufscg.com
2009/08/01: vxvtvhik.com gcuekdss.com
2009/08/02: wjbijxix.com ubhxghvt.com
2009/08/03: wjbijxix.com vcdgcseb.com
2009/08/04: wjbijxix.com ugfdvxck.com
2009/08/05: wjbijxix.com wdbbgwej.com
2009/08/06: wjbijxix.com fgugcijb.com
2009/08/07: wjbijxix.com twsssthu.com
2009/08/08: wjbijxix.com bfithbdd.com
2009/08/09: ufcsbgsg.com cgkgttfg.com
2009/08/10: ufcsbgsg.com fxxubvcg.com
2009/08/11: ufcsbgsg.com egihvgjf.com
2009/08/12: ufcsbgsg.com fkcxifec.com
2009/08/13: ufcsbgsg.com ukxsuvhw.com
2009/08/14: ufcsbgsg.com fxkihkfi.com

ProjectEuler problem 144

2009-03-09T11:19:00.007+01:00

Project Euler is a website offering math challenges solvable by programming - usually few tens lines of code are enough. Last friday, after more than a year of Euler abstinence, I decided to have a look at it again, and ran across this cool problem (#144, check it out here).

So the goal is to find the number of times the laser beam will hit the ellipse-shaped cell before exiting through the input cavity.
First, let's formulate the problem with simple trigonometry. Have a look at the schema below:

The laser beam comes from A and hits the ellipse at point 0. We can calculate the slope m0: (yO-yA)/(xO-xA); we can also calculate the slope m1: -4*x/y. We need to calculate slope m2 and deduce B in order to iterate this process (find the next point of impact).

It appears clear that:
a = a0-a1
and
a = a1+PI-a2

Therefore:
tan(a) = tan(a0-a1)
= (tan(a0)-tan(a1))/(1+tan(a0)*tan(a1))
= (m0-m1)/(1+m0*m1)

and
tan(a) = tan(a1+PI-a2)
= tan(a1-a2)
= (tan(a1)-tan(a2))/(1+tan(a1)*tan(a2))
= (m1-m2)/(1+m1*m2)

Let's set X = (m0-m1)/(1+m0*m1)
X = (m1-m2)/(1+m1*m2)
-> m2 = (m1-X)/(1+X*m1)

We have the slope m2 of the reflected beam (OB). With the coordinates of O (x0,y0), we have the equation of the line:
y = a*x+b, with a=m2 and b=y0-m2*x0

The last step is calculate the coordinates of B. We have:
- the equation of the ellipse: 4*x^2+y^2 = 100
- the equation of (0B): y = m2*x+b

It boils down to solving the quadratic:
x^2*(4+a^2) + x*(2*a*b) + (b^2-100) = 0

And then we yield the coordinates of B. After a few 300-and-something iterations (nah I wouldn't spoil your Euler fun) you'll find out the reflected point falls onto the exit hole. Problem solved!

Sudoku solver

2009-03-04T20:42:00.004+01:00

Nothing new or original here.
This Sudoku solver just aims to show how compact Python code can be...
The core of this piece of code is less than 40 lines of code. And we could do much better than that.

Real-time stock quotes Python API

2009-02-14T18:03:00.004+01:00

I've put up a handy script on my Google code area right here.

This Python module works like a very simple interface to get stock quotes from the French stock website Boursorama. You can get securities of any trading place providing you know its ISIN of course.

The cool stuff about it is that it gives you real-time quotes (yes, you avoid the 15/20-min delay Yahoo and co. give you).

Here's how to use it:


$ from pybourso import get_stock
$ e = get_stock('US38259P5089')
$ print e['name'], e['value'], e['variation']

GOOGLE INC, 357.66, -1.49

Check out the source to see all that's returned by get_stock(). Enjoy!

csheap

2009-02-09T21:00:00.002+01:00

csheap is a customizable dynamic memory allocator written in C. It was originally written as a replacement for the standard libc malloc and the Windows runtime.

I've put it up on Google Code here. Enjoy.

pushfd and popfd are slow...

2009-01-08T17:51:00.002+01:00

...damn, damn slow!
Use lahf/sahf instead.
A few numbers later on - if I have time.

Why gambling on online Poker sites is a bad idea

2008-09-20T20:15:00.000+02:00

On top of being forbidden by law in many countries, gambling online is not the smartest idea one may have.

Poker is meant to be played in real life: you're supposed to see, even feel, your opponents. This process implies close surveillance: would you allow your real-life Poker friends to have their 'Poker maths' and 'Poker stats for dummies' at arm's reach. I'd certainly not.

When you're playing online, you may or may not be cheated in such ways. How would you? For instance, I know two people playing Hold'em together online, exchanging their hands over IM and sharing their profit. OK, it's far from organized crime... but we could easily imagine programs analyzing the board, eventually exchanging information with other programs playing at the same table, and reaching a decision together in an automated fashion.

Simpler, a bot could easily analyze the board, compute winning odds, and give the human player a decision hint.

For fun (and NOT profit), I coded a proof-of-concept program. It's meant to analyze tables of a well- known online Texas Hold'em program, compute and display odds. Inoffensive, but this would be the first and most important step of a "poker bot".

I prefer not to give names here... Anybody familiar with online poker will easily figure them out anyways. Here's the table (with many elements blurred out or removed):

The analyzer program output is:

Here, I'm triggering an analysis manually. Primitive OCR routines read table information, such as player positions, who's got the button, private cards, common cards, etc. Then, a separate component simulates thousands of games based on the information fed by the OCR component, and finally displays more or less useful statistics.

In our example, we have As,6h, the stage is (River;9s,Ad,4s,Tc,Jc) and we're competing against 3 other players. The estimated odds are 24.6% (for an average 25% since we're 4 players). This ratio may be used as a hint by a human player, or, if the program is extended (pot and players' stacks analysis, etc.), could be used as a building block for a fully automated poker-playing program...

This is a basic PoC code, nothing exceptionnal here. We could easily imagine that bad guys have poker bots in place; now, how would you feel being the sucker competing against 9 bots exchanging cards... play money's fine, real money's a different story.

Getting free Velib' w/o getting tired

2008-09-17T12:13:00.009+02:00

A cool thing about Paris is its public bicycle system, called Velib'. The concept is fairly simple: for 30 euro a year, you can take and use any bicycle available around the ~1000 stations spread across the city.

The rules: You may take your Velib' at point A and give it back at point B. You may use it up to 30 minutes for free; if you use it more than that, you will pay (1 euro for the next half-hour slice, and so on).

The downside of the system is that a few stations, mainly these located at higher altitudes, were usually empty, whereas stations close to them, but at lower altitudes, were packed very quickly (for obvious reasons).

This problem was solved a few months back, when about 10% of the stations (*mainly*, the highest-located ones) were converted to V+ stations. The concept is simple: When you borrow a bicycle in a regular station and bring it back to a V+ one, you get extra credit. This virtual money can then be used to pay your extra time when you borrow a Velib' for more than 30 minutes.

Now, you see where I'm going! Some V+ stations are really close to regular stations, as you can see on this page. But how close exactly? And which ones are the best spots, ie, V+ super close to a V stations? Filling up an account with extra credit might not be that exhausting after all...

The GMap map used on the above page is fed with Velib' stations data from the following XML feed. It contains the station names, addresses, geo-coordinates, as well as flags (is the station in operation? is it a bonus station?).

If we calculate primitive euclidean distances between 2 stations using their (longitude; lattitude) coordinates, omitting the altitude, we could easily figure out, for each of the 90 operating V+ stations, which regular station is the closest...

Now, I'll spare you the code (very easy to write, check it out here), and will go straight to the best results. The format is (V+, V, distance):


09018 - PLACE PIGALLE > 09019 - VICTOR MASSE (0.000919)
09004 - ROCHECHOUART GERANDO > 09006 - TRUDAINRE ROCHECHOUART (0.000945)
18043 - BLANCHE > 09027 - FONTAINE DOUAI (0.001091)
14030 - LOSSERAND - PERNETY > 14104 - LOSSERAND BOYER-BARRET (0.001106)
18041 - MARTYRS 2 > 09017 - TRUDAINE MARTYRS (0.001140)
...

Let's visually check our best couple on the map, which are stations 09018 and 09019:

Yep, seems OK to me. One might go to Pigalle for *different* reasons after all...

Rar(e) juicy bits

2008-09-14T16:17:00.000+02:00

I recently spent time working on the Rar algorithm. Though the compression routines are not disclosed, Eugene Roshal freely provides the sources for the command line version of its decompressor. It’s the only real pieces of information available out there – the other documents you may find concern the archive file format itself.

A few context elements first: Several versions of the Rar program exist, along with different major versions of the algorithm behind it. The one we're interested in is version 2.9, the algorithm in use in Rar version 3. Version 2.9 compresses blocks of data using either a Lempel/Ziv or a PPM (Prediction by Partial Matching) algorithm.

The interesting thing is that special symbols can be found in the compressed data stream to notify the presence of VM bytecode. Yes, you read right: v29 makes use of a virtual machine. The VM code is interpreted after decompression, and is used for unfiltering the data.

To achieve better compression ratios, data is usually filtered/modified by a compressor program - ie, a filter's goal is to decrease the entropy of the data to be compressed. A very common example is when compressing x86 binary files: relative jumps and calls (0xE8, 0xE9) can be replaced by their fake, absolute equivalents. A jmp $+5 (E8 00 00 00 00 ) at offset 0x100 would be replaced by E8 05 01 00 00. This filter is used by various executable packers (ex: AsProtect), as well as compressors (ex: SevenZip, Rar) or installers (ex: InnoSetup).

Version 2.9 makes use of several filters, for images, videos, audio files, binary files, etc. However, in this very case, the unfiltering routine is encoded in the compressed stream itself, with the use of the VM bytecode. That’s where v29 potentially allows more flexibility than other compressor programs.

Available VM opcodes are the following (check out vmrar.hpp):
VM_MOV, VM_CMP, VM_ADD, VM_SUB, VM_JZ, VM_JNZ, VM_INC, VM_DEC, VM_JMP, VM_XOR, VM_AND, VM_OR, VM_TEST, VM_JS, VM_JNS, VM_JB, VM_JBE, VM_JA, VM_JAE, VM_PUSH, VM_POP, VM_CALL, VM_RET, VM_NOT, VM_SHL, VM_SHR, VM_SAR, VM_NEG, VM_PUSHA,VM_POPA, VM_PUSHF,VM_POPF, VM_MOVZX,VM_MOVSX,VM_XCHG, VM_MUL, VM_DIV, VM_ADC, VM_SBB, VM_PRINT, VM_MOVB, VM_MOVD, VM_CMPB, VM_CMPD, VM_ADDB, VM_ADDD, VM_SUBB, VM_SUBD, VM_INCB, VM_INCD, VM_DECB, VM_DECD, VM_NEGB, VM_NEGD, VM_STANDARD

Looks very similar to x86 opcodes, isn't it? If you go through this whole list, you may wonder what VM_STANDARD stands for? Well, without this opcode, reversing standard filters would be incredibly slooooow! VM_STANDARD instructs the VM that a standard filter is used, and that a hard-coded decoding routine can be executed to speed the process.

VM_STANDARD is not found in the bytecode stream per se, but is generated by the program when the bytecode stream exhibits characteristics such as particular length and crc:


VM_StandardFilters RarVM::IsStandardFilter(byte *Code,int CodeSize)
{
struct StandardFilterSignature
{
  int Length;
  uint CRC;
  VM_StandardFilters Type;
} StdList[]={
  53, 0xad576887, VMSF_E8,
  57, 0x3cd7e57e, VMSF_E8E9,
 120, 0x3769893f, VMSF_ITANIUM,
  29, 0x0e06077d, VMSF_DELTA,
 149, 0x1c2c5dc8, VMSF_RGB,
 216, 0xbc85e701, VMSF_AUDIO,
  40, 0x46b9c560, VMSF_UPCASE
};
uint CodeCRC=CRC(0xffffffff,Code,CodeSize)...

Here’s an example: The stream is being decompressed; the current symbol is 0x101, which instructs the decompressor that VM bytecode is to be read (check out unpack.cpp). The bytecode is processed; it contains VM initialization values, as well as a VM opcode sequence. Now, when the filter is to be applied, the opcodes could be processed one by one. Emulating hundreds of VM_MOV, VM_CMP and others is a computationally expensive task. Therefore, what the decompressor does first is to check the opcode sequence length and CRC against a list of known VM routines. These routines are for commonly used filters. If one of these standard routines is matched, then a VM_STANDARD opcode is generated, its operand being the VMSF_Xxx constant referring to the hardcoded routine executed instead of bytecode emulation.

So far, 6 standard filters routines are available:
- x86 jumps and/or call filters (VMSF_E8, VMSF_E8E9)
- Intel Itanium filter (VMSF_ITANIUM)
- RGB filter (VMSF_RGB)
- Audio files filters (VMSF_AUDIO)
- Image filters (VMSF_DELTA)
- Case filters (VMSF_UPCASE)

This choice of having a VM to run the filters offers extension possibilities yet to be seen, maybe via the use of plugins in later versions of Rar? One could then create a special filter, designed to achieve very good compression ratios with particular files. Not to mention that the filters can be organized in a filter stack, reused, and applied one after each other, etc. Quite powerful.

Last thing: how do you decide which filters are applied to your compressed data? Well, you quite don’t. The compressor will decide for you (let me remind you that they’re all closed source). Hmm... going back to Unrar source code, it appears cmddata.cpp contains the code responsible for handling command line parameters of Unrar. In fact, cmddata.cpp contains command line options for Rar and Unrar (it’s very likely that the sources are a subset of Rar+Unrar sources, and the compilation of a specific program is decided via a pre-processor #define).

You may notice that the switch –mc allows the user to force-enable/disable the use of a particular filter:


case 'M':
  switch(etoupper(Switch[1]))
  {
  case 'C':
    // ...cut...
    switch(etoupper(*(Str++)))
    {
      case 'T': Type=FILTER_PPM; break;
      case 'E': Type=FILTER_E8; break;
      case 'D': Type=FILTER_DELTA; break;
      ...

PPM is a compression mode; it has the role of a dummy filter here. Let’s fire Rar command-line now, to see if these options are advertised:


$ rar -h
Usage:  rar command -switch1 -switchN archive files ...
(cut)
mcX    Set advanced compression parameters

What does "advanced compression parameters" mean? It seems RarLab is not quite ready to let their users decide what filters they would like to use, let alone code their own filters via the use of the VM.

If you want to know more, well, check out the Unrar source code, more specifically unpack.cpp/hpp, rarvm.cpp/hpp and cmddata.cpp.