Monday, October 27, 2014

Elisp: String Compare (Less than)

Less Than

There are many elisp functions for comparisons. The "less than" sign < is a mathematical sign to compare inequality. Elisp has the function < to compare Number or Marker.

(< 1 2)
(< 2 1)

It is obvious enough that no explanation is needed.

String Less Than

Elisp also has a "less than" function for Strings, called string-lessp.

(string-lessp "abc" "def")
(string-lessp "abc" "ab")

It is a predicate function, meaning that it returns t if the first string, "abc" in the first example, is less than the second strings "def", or nil otherwise.

Elisp have a convention, as noted in elisp info, to end a predicate function with letter "p". Thus, following this convention, string-lessp ends with "p".

Elisp does have string< as an alias for string-lessp. So that you can write the above example:

(string< "abc" "def")
(string< "abc" "ab")

"<" vs "p" vs "-p"

It seems like a majority of "less than" functions follow this "lessp" convention, however, there are other functions in Emacs. Here is an incomplete list of "less than" functions I have got from my Emacs with M-x apropos <$\|lessp$\|less-p$.

What functions do you have in your Emacs?

Incomplete List of "less than" functions

  • <
  • <<
  • bibtex-lessp
  • byte-string<
  • coding-system-lessp
  • customize-version-lessp
  • elmo-time-less-p
  • elmo-time<
  • file-attributes-lessp
  • gnus-pseudos<
  • gnus-string<
  • ido-file-extension-lessp
  • ido-file-lessp
  • mailcap-viewer-lessp
  • org-entries-lessp
  • org-table-formula-less-p
  • org-time<
  • recentf-string-lessp
  • s-less-p
  • skk-string-lessp-in-coding-system
  • skk-string<
  • string-lessp
  • string<
  • time-less-p
  • version-list-<
  • version<

Monday, April 23, 2012

mruby first impression

Matz released mruby, a yet another ruby implementation for small systems, at GitHub. Mruby is a new implementation of Ruby Language based on RiteVM, which seems to be a register based VM with tri-color marking and mark-and-sweep collector GC.

I'll just quick look at the following points on the VM, which is said to be the most costly part of any virtual machine[1].

  • The Instruction Dispatcher
  • Accessing the Operands
  • Performing the Computation

The instruction dispatcher

The instruction dispatcher, mrb_run(), is a simple C switch dispatcher. There seems to be a compile time condition code for a label dispatcher, too, but the default one is the C switch.

The instruction dispather is compiled to 17200 bytes (0x4330 bytes) of function under GCC 4.3 for ARM (the number depends on compiler options, of course). I haven't checked how this works in any type of ARM CPU cache.

$ objdump -t vm.o |grep mrb_run
000001d8 g     F .text  00004330 mrb_run

Accessing the Operands

The VM instructions are encoded in 32 bit fixed size instruction set. There seems to be three types of instructions. You can find this out in src/opcode.h.

The opcode is 7 bit long, which means that RiteVM can support 127 opcodes. There already are 75 opcodes and five reserved opcodes defined in src/opcode.h. So, 6 bit (64 opcodes) is too short RiteVM.

If you look at the comment above, it seems to be that the opcode is at MSB, but it is actually at the LSB side.

So, it's more like A:B:C:OP instead of OP:A:B:C.

A:B:C:OP takes three operands, the first two are 9 bits each and the last one is 7 bits. So, to retrieve the operand A from this vm instruction, you need to shift 23(9+7+7) bits to the right. You can do that in one instruction on ARM CPU.

A:Bx:OP takes two operands, the first one is 9 bits and the second one is 16 bits.

Ax:OP takes one 25 bits operand.

Performing the Computation

I'm still not sure how much computation is required for each instructions. This is fun to try but takes some time.

Register files

I also checked mruby registers. They are an array of mrb_values, which is a union of C variables and a byte for type indicator, as you can see below.

Friday, March 02, 2012

Virtual Machines and Bytecode Architecture

I was curious about types of popular VMs / bytecodes. So here is a result of quick survey I did:

Register based

Stack based

  • Java VM
  • CPython
  • CIL
  • Sqlite 3.4.4 and earlier

Abstract Syntax Tree based

Monday, November 10, 2008

Android loves small LCD, too

One of my colleague just finished hooking up a small LCD to Armadillo-500 FX! Android seems to be happy at this lovely new home. I just can stop thinking about what I can do with this tiny, cell phone sized, combo dev toy.

This hack was to show that FX works just fine with other LCD, or any LCD per se, than the default 5.7 inch one. Hope everyone gets the idea.

This will be showed off at ET2008(link is to japanese page...). Hope to see you guys there.

Thursday, May 08, 2008

Armadillo Panel Computer

Hmm.. It seems like shaping up quite nicely.

Thursday, November 22, 2007

Android - Runs on a real hardware

Here is a clip to show you Android running on a real hardware, Armadillo-500.

All credit is due to Ben "Benno" Leslie for his incredible work. All I've done is put them together.

By the way, the kernel is compiled as OABI with two additional feature enabled.
  • EABI support
  • OpenBinder

The kernel itself doesn't have to be EABI to run EABI binaries.

Android - OpenBind: protocol doesn't match!

It seems like some people are trying to get as much OpenBinder information on the Android Internals.

I've downloaded OpenBinder source code archive from Dianne Hackborn's site, fixed a few places to meet the current API, compiled, put it on my board and still can't make Home App to run.

So, I've downloaded strace binary from Benno's page and run system_server under it. Now, I've got:

open("/dev/binder", O_RDWR|O_LARGEFILE) = 7
fcntl64(7, F_SETFD, FD_CLOEXEC) = 0
ioctl(7, 0xc0046209, 0xbecdac9c) = 0
writev(4, [{"\6", 1}, {"ProcessState\0", 13}, {"Binder driver protocol does not "..., 59}], 3) = 73

Binder driver protocol does not match user space protocol!

Ouch.... I can go disassemble ioctl() to see how the application is checking binder version. However, if Android components are using new feature, there is no way I can re-implement that feature. I guess I have to wait for code to be open. Sigh...

Tuesday, November 20, 2007

Android - Binder

I haven't been able to run android on my arm platform. I have been too lazy to compile strace to see what's going on. Fortunately, Benno have been working on it and it seems like he's successfully got a strace log.

He's log reveal that the android depends on /dev/binder which is not a standard feature on my kernel. Here is the snippet from his log.

This bit here is pretty important. /dev/binder is the character device for OpenBinder, which is something that you see in the kernel source. This appears to be an IPC sub-system for the Linux kernel. It was at some stage donated by Palm, and there was an website for sometime, although that site is now dead. Finding more information on this will be essential.

05:30:51.733954 open("/dev/binder", O_RDWR|O_LARGEFILE) = 7
05:30:51.735488 fcntl64(7, F_SETFD, FD_CLOEXEC) = 0
05:30:51.736483 ioctl(7, 0xc0046209, 0xbef86cbc) = 0
05:30:51.737443 ioctl(7, 0x40046205, 0xbef86cb8) = 0
05:30:51.738385 mmap2(NULL, 8388608, PROT_READ, MAP_PRIVATE|MAP_NORESERVE, 7, 0) = 0x40008000

As he said, is already down. But, I've found a link to OpenBinder Documentation on #android.

I haven't read the doc yet but it seems like this is required to run android on my system.