Mr Foo

CAR, CDR, CONS - an aside

2012-01-31T12:53:00.001+01:00

Commenter pcpete has been following the ARM OS stuff, but was having some trouble with my CAR/CDR/etc macros. I figured I'd do a little writeup for those who aren't totally au fait with what that's all about.

CAR, CDR and CONS are terminology which has stuck around since the '50s. It's not going away, so if you want to Lisp, you need to get used to it.

The original Lisp was implemented on the IBM 704 computer. This was a machine which had a 36 bit word (peculiar, but useful) and a 15 bit address bus. 36 bit words could be split into 4 parts (and hardware support was provided for doing so) known as the address (a 15 bit value), the decrement (again, 15 bits), the tag (3 bits) and the flags (3 bits). The very earliest work on Lisp provided operators to extract these 4 parts (Contents of Address part of Register or CAR, and likewise for Decrement, Tag and Flags, providing CDR, CTR and CFR). Later work (before the first implementation of Lisp) dropped direct manipulation of flags and tag, leaving CAR and CDR, and a "Construct" operator, CONS, which took values for the address and decrement parts respectively and stuffed them into a machine word.

The fact that a machine word was bigger than the size of the address of a machine word meant that it was possible to implement pairs of values and singly linked list cells within one machine word. A pair of values (for example, 1 & 2) could be created as follows:

CONS(1, 2)

and singly linked lists by treating the 'address' part (paradoxically enough) as a value, and the 'decrement' part as the address of the next cell in the list. By setting the last pointer to some easily-recognised value (known as 'nil'), it is possible to find the end of a list. Thus, creating a list containing the numbers 1, 2 and 3, looks like this:

CONS(1, CONS(2, CONS(3, nil)))

Binary trees are also easy to construct using pairs - for example:

CONS(CONS(1, 2), CONS(3, 4))

I'm generally the last one to point people at Wikipedia, but there's a reasonable and rather more graphical explanation of what have become known as 'cons cells' over there.

It's worth noting that Lisp also allows you to use the notation 'first' and 'rest' instead of 'car' and 'cdr', although this only really makes sense when in list context, and doesn't allow for composition (caar, cadr, cdar, etc). Pretty much nobody uses first and rest.

So, Lisp uses what is, in effect, a pair (or list) oriented memory model as opposed to the more usual (these days) approach of addressing single memory cells individually. And if one is implementing a Lisp (as I am), it makes a certain amount of sense for the low level memory allocation and manipulation functions to operate in this way. Unfortunately, "modern" machines in general don't have words that are larger than their address bus size, and ARM is no exception to this. ARM is a 32 bit machine - we could restrict addressing within our lisp to 16 bits (maximum 64Kwords or 256KB) and all values to 16 bits, or, more sensibly, use "virtual" words of 2 machine words (or maybe more) in size. Usefully, ARM has LDRD (Load Register Dual) and STRD (Store Register Dual) operands that make this a snip to do.

So, we can define cons cells as 8-byte aligned pairs of 32-bit values, manipulate them as pairs using LDRD/STRD, and we're a long way towards implementing a Lisp.

But what of the Flags and Tag stuff that was originally in Lisp? Although, by the time Lisp came out, you had no way of directly manipulating them, they were still used to differentiate between pointers, direct values, and constants, amongst other things. And this is something we need to be able to do as well, otherwise we can't tell if (for example) the value 0x00000000 in the CDR of a cell is a pointer to a cell at the address 0x00000000, the integer value zero, or some special value indicating nil/end of list.

As it happens, all is well. LDRD/STRD require an 8-byte aligned address, which means the low 3 bits of a pointer will *always* be 0. We can, therefore, use those 3 bits as flags to indicate various other types, and, if we're careful, we can encode the majority of types in such a way as to keep their values "boxed" (i.e. containable in a 32 bit value). Values requiring more than 32 bits to encode (strings, large numbers, rational numbers, etc) can either be encoded as lists of boxed values, pairs, or using any other encoding the programmer deems useful as long as they are easily recognisable.

So, back to the code I posted, which uses CAR, CDR, SET_CAR and SET_CDR macros.

/* linked list structure */
typedef struct task_list {
task_t * _car;
struct task_list * _cdr;
} task_list_t;

/* some LISPy primitives */
#define CAR(x) (x)->_car
#define CDR(x) (x)->_cdr

#define SET_CAR(x,y) CAR(x)=(y)

#define SET_CDR(x,y) CDR(x)=(y)

As we can see, task_list_t is an analogue for the cons cell, being simply 2 address-bus sized values held together. Indeed, my code elsewhere looks like this:

typedef cons_t task_list_t;

but the original formulation is perhaps easier to grok at first.

So, given a pointer x to a cons cell c, we can see that CAR(x) expands to(x)->_car, in other words returning the _car element of the cell c pointed to by x. Likewise SET_CAR(x, y) becomes (x)->_car = (y), assigning the value y to the _car element of the cell c pointed to by x. Doing this as macros is probably premature optimisation, but it's "the done thing".

Our task scheduler uses a list (actually, a plurality of lists) of tasks to execute, and considers them for execution in a "round robin" style. So, assuming we have 4 tasks, a, b, c and d, we might have a list that looks, in lisp syntax, like this:

(a b c d)

or, in diagram form, where the top row is the CDR of the cell, and the bottom the CAR, and * indicates a pointer to the next cell

* - * - * - nil
| | | |
a b c d

We need to rotate the list as we consider each task, so that the next time through we consider the next task. So after considering task a for execution, we want the list to look like this:

(b c d a)

or, in diagram form

* - * - * - nil
| | | |
b c d a

In true lisp style, we'll use a singly linked list for this, with the CAR of each cell being a pointer to the task, and the CDR being a pointer to the next cell, or nil for end of list.

So, we come in, and we find the CAR and CDR of the (original) list. CAR is, obviously enough, task 'a', the task we want to consider for execution. CDR, however, is not task b, but the rest of the list (hence the alternative 'rest' in Lisp) - i.e.

(b c d)

or, in diagram form

* - * - nil
| | |
b c d

So our next step is to put 'a' onto the end of the list. This is not as simple as it seems - CONS can only be used to push items onto the front of a list - CONS(list, a) would result in this:

((bcd) . a)

or, in diagram form

a
|
* - * - nil
| | |
b c d

which is not a true list in Lisp terms (it's a "dotted pair" with a list as its first element). We need some sort of APPEND operator that adds an element to the end of a list, a sort of 'reverse cons'. Lisp has one of those, it's (oddly enough) called APPEND, it's usually defined recursively, and it always creates new cons cells all over the place. We really don't want to go allocating new memory in a function that's going to be called thousands of times per second simply to move a few values about - we want to keep the same cons cells and simply swap their CDR values around. The algorithm thus becomes:

first := list
if CDR(first) != NIL
list, end := CDR(first)
end := CDR(end) while CDR(end) != NIL
SET_CDR(first, NIL)
SET_CDR(end, first)

With that in mind, have another read through http://stm8sdiscovery.blogspot.com/2011/12/developing-multitasking-os-for-arm-part_14.html

Simon

Developing a multitasking OS for ARM part 3 3/4

2012-01-16T09:32:00.002+01:00

So, we looked at how to do the difficult part of task swapping last time, now let's look at how we go about handling interrupts and the syscall layer.

Firstly, interrupts. We'll not bother with FIQs for the moment, we'll stick with IRQs.

Despite having an ARM1176 core, the Raspberry Pi (or, rather, its Broadcom SoC) doesn't have a vectored interrupt controller - instead it has 3 "standard" ARM interrupt controllers. That makes things a bit more complex for interrupt handling, but it's not too arduous. As a quick reminder, here's the IRQ code we had before, with a little bit of meat in the middle:

.global _irq_handler

_irq_handler:
sub lr, lr, #4 /* Save adjusted LR_IRQ */
srsdb sp!, #SYS_MODE /* save LR_irq and SPSR_irq to system mode stack */

cpsid i,#SYS_MODE /* Go to system mode */

push {r0-r12} /* Save registers */

and r0, sp, #4 /* align the stack and save adjustment with LR_user */
sub sp, sp, r0
push {r0, lr}

/* Identify and clear interrupt source */
/* Should return handler address in r0 */
bl identify_and_clear_irq

blxne r0 /* go handle our interrupt if we have a handler */
/* An interruptible handler should disable / enable irqs */

/* Exit is via context switcher */
b switch_context_do

and the context switcher looks like this:

.global switch_context_do

switch_context_do:

/* Do we need to switch context? */

mov r3, #0x0c /* offset to fourth word of task block */

ldr r0, =__current_task

ldr r1, [r0]

ldr r0, =__next_task

ldr r2, [r0]

cmp r2, #0 /* If there's no next task, we can't switch */

beq .Lswitch_context_exit

cmp r1, #0 /* In the normal case, we will have a __current_task */

bne .Lnormal_case

/* When we get here, we're either idling in system mode at startup, or we've */

/* just voluntarily terminated a task. In either case, we need to remove the */

/* return information we just pushed onto the stack, as we're never, ever going */

/* back. */

pop {r0, r1} /* remove any potential stack alignment */

add sp, sp, r0

add sp, sp, #0x3c /* and the other registers that should be there */

/* r0-r12, interrupted pc & spsr */

/* Now we can do our first actual task swap */

ldr r0, =__next_task /* swap out the task */

ldr r2, [r0]

ldr r0, =__current_task

str r2, [r0]

ldr sp, [r2, r3] /* and restore stack pointer */

b .Lswitch_context_exit /* bail */

.Lnormal_case:

cmp r1, r2 /* otherwise, compare current task to next */

beq .Lswitch_context_exit

clrex /* Clear all mutexes */

/* At this point we have everything we need on the sysmode (user) stack */

/* {stack adjust, lr}_user, {r0-r12}_user, {SPSR, LR}_irq */

/* Save our stack pointer, and swap in the new one before returning */

ldr r0, =__current_task /* save current stack pointer */

ldr r0, [r0]

str sp, [r0, r3] /* stack pointer is second word of task object */

ldr r0, =__next_task /* swap out the task */

ldr r2, [r0]

ldr r0, =__current_task

str r2, [r0]

ldr sp, [r2, r3] /* and restore stack pointer */

.Lswitch_context_exit:

pop {r0, lr} /* restore LR_user and readjust stack */

add sp, sp, r0

pop {r0-r12} /* and other registers */

rfeia sp! /* before returning */

The context switcher looks complex, but it isn't really. There's 4 cases to cater for, viz:

No 'next' task, don't switch
No 'current' task, switch to 'next' task, cleanup stack and switch to 'next' task
'next' task is the same as 'current' task, don't switch
'next' task is different from 'current' task, switch

Obviously, the meat of the interrupt handler is held in 'identify_and_clear_interrupt', which does pretty much what it says on the tin. In this article, I'll show the handler for the qemu platform, which is significantly simpler than that for the Pi, but the Pi handler looks largely the same modulo having to deal with 3 controllers.

.global identify_and_clear_irq

identify_and_clear_irq:

FUNC identify_and_clear_irq

ldr r4, =.Lirq_base

ldr r4, [r4]

/* read the vector address to indicate we're handling the interrupt */

ldr r0, [r4, #IRQ_HANDLER]

/* which IRQs are asserted? */

ldr r0, [r4, #IRQ_STATUS]

ldr r5, =__irq_handlers

clz r6, r0 /* which IRQ was asserted? */

mov r1, #1 /* make a mask */

bic r0, r0, r1, lsl r6 /* clear flag */

str r0, [r4, #IRQ_ACK] /* Now acknowledge the interrupt */

str r0, [r4, #IRQ_SOFTCLEAR] /* and make sure we clear software irqs too */

ldr r0, [r5, r6, lsl #2] /* load handler address */

.Lret: bx lr /* exit */

.Lirq_base:

.word IRQ_BASE

.bss

.global __irq_handlers

__irq_handlers: .skip 32 * 4

and patching in a hander is as simple as setting the address for the interrupt handler into __irq_handlers at the appropriate place. Simples, as they say in internet-land.

Syscalls are very similar. Here's the syscall handler:

.global _svc_handler

_svc_handler:

srsdb sp!, #SYS_MODE /* save LR_svc and SPSR_svc to sys mode stack */

cpsid i,#SYS_MODE

push {r0-r12} /* Save registers */

and r0, sp, #4 /* align the stack and save adjustment with LR_user */

sub sp, sp, r0

push {r0, lr}

ldr r0,[lr,#-4] /* Calculate address of SVC instruction */

/* and load it into R0. */

and r0,r0,#0x000000ff /* Mask off top 24 bits of instruction */

/* to give SVC number. */

ldr r2, =__syscall_table /* get the syscall */

ldr r3, [r2, r0, lsl#2]

cmp r3, #0

beq _syscall_exit

tst r3, #0x01 /* what linkage are we using */

bxeq r3 /* ASM, just run away */

bic r3, r3, #0x01

blx r3 /* C, must come back here */

.global _syscall_exit

_syscall_exit:

pop {r0, lr} /* restore LR_user and readjust stack */

add sp, sp, r0

pop {r0-r12} /* and other registers */

rfeia sp! /* before returning */

.section .bss

.global __syscall_table

__syscall_table:

/* leave space for 256 syscall addresses */

.skip 2048

The fun bit is how we go about getting the syscall number into the handler. I've taken the "canonical" approach of using the svc operand, hence the bit where we get the instruction and extract the number. Other ways include using a register, a global variable, pushing onto the stack, or some combination of these.

The other twist here is that I allow for both C and assembler syscall functions by setting (or not) bit 0 of the function address in the syscall table. Assembler syscall handlers must, of course, exit via _syscall_exit or equivalent, but that's down to the programmer to get it right.

Developing a multitasking OS for ARM part 3 1/2

2012-01-07T10:16:00.002+01:00

Okay, so last time we looked at what we need to schedule and store top level information about tasks in our fledgling OS. And it was pretty easy to do, because we could do all of it in C. Unfortunately, things are about to get complicated again, because we're about to dive down into assembler again.

Whoopee! I can almost hear the sound of "back" buttons being clicked as I type this.

So. Multitasking. How's that gonna work, then? Largely speaking, there's 2 types of multitasking - preemptive multitasking, where tasks run for a specified amount of time then get forcibly swapped out, and cooperative multitasking, where tasks run until they decide to give some time to someone else. We're going to implement (because there's precious little overhead in doing so) a hybrid where tasks can be "nice" and give time to others, but where the absolute maximum time they get is capped by a preemptive scheduler.

So. Let's look at the sequence of events for a user-triggered task swap. We want the user to use a line of code that looks like this (remember, I'm developing something that runs scheme...)

(task-swap-out)

However, the user's code is running in user mode (remember the ARM processor states), and it can't directly access the task scheduler. This is where software interrupts / SVC calls come in - the user's code *can* use the svc instruction. This, in fact, is the beginning of what is known as a syscall interface, the way that unprivileged user code calls (or causes to happen) kernel functions.

Executing the svc instruction causes the following to happen:

CPSR_usr is transferred to SPSR_svc
PC is stored in LR_svc
Processor switches to SVC mode (SP_usr and LR_usr are now hidden by SP_svc and LR_svc, CPSR is identical except for processor state change)
PC is loaded with the address of the SVC exception handler

At this point, what we need to do is store R0-R12, LR_usr and PC (before entry to svc handler) into the user stack, in a known order, then save the user stack pointer to the task's "housekeeping" information, load the equivalents back in for the next task, and jump out of the handler back to user code. We'll get onto that in a minute.

Preemptive task swapping will be done by using a timer interrupt. Thus, for a preemptive task swap, the situation is quasi-identical, with _svc above replaced by _irq. The only difference is that the PC stored to LR_svc is actually 4 bytes on from where we want to restart, so we need to remember to take that into account.

So. How do we go about saving our information to the user stack? This is made quite easy by the fact the user mode register are identical to the system mode registers. So we need to save the svc/irq mode stuff (LR, SPSR) into the system mode stack, then swap into system mode and save the rest. The first bit is covered by one instruction, which might have been made for the task:

srs (Store Return State) - store LR and SPSR of the current mode onto the stack of a specified mode

and, of course, its "twin"

rfe (Return From Exception) - load PC and CPSR from address

So, the preamble for the svc handler is as follows:

FUNC _svc_handler
srsdb sp!, #SYS_MODE /* save LR_svc and SPSR_svc to svc mode stack */
cpsid i,#SYS_MODE /* go sys mode, interrupts disabled */

push {r0-r12} /* Save registers */

and r0, sp, #4 /* align the stack and save adjustment with LR_user */
sub sp, sp, r0
push {r0, lr}

and for an irq:

FUNC _irq_handler

sub lr, lr, #4 /* Save adjusted LR_IRQ */

srsdb sp!, #SYS_MODE /* save LR_irq and SPSR_irq to system mode stack */

cpsid i,#SYS_MODE /* Go to system mode */

push {r0-r12} /* Save registers */

and r0, sp, #4 /* align the stack and save adjustment with LR_user */

sub sp, sp, r0

push {r0, lr}

Note that the only difference is that the irq handler adjusts the return address (as we want to go back to the interrupted instruction, not the next one).

Given that we are now *always* in system mode, exiting from either handler is identical:

pop {r0, lr} /* restore LR_user and readjust stack */

add sp, sp, r0

pop {r0-r12} /* and other registers */

rfeia sp! /* before returning */

I'll move onto how to implement the guts of the two handlers in the next post. But before we go, here's how we set up a task in "C" land.

Remember, when we switch into a task, we will be pulling a stored process state from the task's stack into the registers, and then restoring the PC and CPSR, also from the task's stack. Setting up a task, then, involves "faking" the preamble of the exception handlers above. Note the use of exit_fn as the value of LR_usr, this is where we go when a task dies, and is used to clean up after task exit, and the use of 'entry' (the address of the task's entry function) as the value of LR_svc/irq, which will be used as the "return" address from the exception handler.

The use of exit_fn means we can schedule "one-shot" tasks (which not all realtime OSs can do). Hooray for us.

// Allocate stack space and the actual object

task_t * task = malloc( sizeof(task_t) );

void * stack = malloc( stack_size * 4 );

unsigned int * sp = stack + stack_size;

task->stack_top = stack;

task->priority = priority;

task->state = TASK_SLEEP;

task->id = (unsigned int)task & 0x3fffffff;

*(--sp) = 0x00000010; // CPSR (user mode with interrupts enabled)

*(--sp) = (unsigned int)entry; // 'return' address (i.e. where we come in)

*(--sp) = 0x0c0c0c0c; // r12

*(--sp) = 0x0b0b0b0b; // r11

*(--sp) = 0x0a0a0a0a; // r10

*(--sp) = 0x09090909; // r9

*(--sp) = 0x08080808; // r8

*(--sp) = 0x07070707; // r7

*(--sp) = 0x06060606; // r6

*(--sp) = 0x05050505; // r5

*(--sp) = 0x04040404; // r4

*(--sp) = 0x03030303; // r3

*(--sp) = 0x02020202; // r2

*(--sp) = 0x01010101; // r1

*(--sp) = (unsigned int) env; // r0, i.e. arg to entry function

if ((unsigned int)sp & 0x07) {

*(--sp) = 0xdeadc0de; // Stack filler

*(--sp) = (unsigned int)exit_fn; // lr, where we go on exit

*(--sp) = 0x00000004; // Stack Adjust

} else {

*(--sp) = (unsigned int)exit_fn; // lr, where we go on exit

*(--sp) = 0x00000000; // Stack Adjust

}

task->stack_pointer = sp;

Developing a multitasking OS for ARM part 3

2011-12-14T10:49:00.002+01:00

Okay. We're almost done with the big bits of scary assembler. Indeed, this post is almost totally assembler free, and will deal with some C functions and definitions we need for later.

We want to do something useful with what we have at the moment. We could simply implement "something useful" as a C language routine called c_entry(), which would run in SVC mode with interrupts off. In some cases, that would be sufficient. But it would hardly count as an OS, let alone a multitasking one.

So, let's look at what we want to do, make some definitions. We want tasks that run in an unprivileged mode (i.e user mode) and are either preemptively swapped out by the OS in order to run another task, or which periodically yield control of the processor to another task. They must be able to terminate. For the moment, we won't worry too much about protected memory spaces, IPC, or any of that jazz (which complicate matters, but which will come later).

A task, must have its own, inviolate, set of registers, and its own stack. It must also have some other information - entry point, state, and potentially priority. My implementation is based on scheme, so a task must also have an environment, but that's not absolutely necessary.

/* function pointer type returning void and taking a pointer to an environment */
typedef void(*task_entry_point_t)(void * environment);

/* potential task states */
typedef enum {
TASK_RUNNABLE,
TASK_SLEEPING,
} task_state_t;

/* And the task itself */
typedef struct {
void * stack_top; /* limit of the task stack */
void * stack_pointer; /* current stack pointer */
uint32_t priority:5; /* priority, 0-31 */
uint32_t state:1; /* state, task_state_t */
uint32_t id:26; /* task id */
} task_t;

Obviously, we need to know what the current task is, and have a list of other tasks that might want to run. This is not identical to my code, as tasks are actually scheme objects, but you get the idea.

/* linked list structure */
typedef struct task_list {
task_t * _car;
struct task_list * _cdr;
} task_list_t;

/* some LISPy primitives */
#define CAR(x) (x)->_car
#define CDR(x) (x)->_cdr

#define SET_CAR(x,y) CAR(x)=(y)

#define SET_CDR(x,y) CDR(x)=(y)

/* We'll need these later */

#define nil (task_list_t*)0

#define skip (task_t*)0

/* And the bits we need for the actual lists */
task_t * __current_task;
task_list_t * __priority_lists[31];

Now, the approach we'll be taking to multitasking is this:
Each task is created with a prority, and positioned as such in one of the priority lists. Every time we need to find a task, we go through the priority lists, starting at zero, and ending at 31. We look at each element in turn of the list by removing it from the head of the list and then grafting it onto the end of the list. This way we round-robin schedule within each priority. Only "runnable" tasks get scheduled, obviously. If the task is actually the placeholder "skip", we will skip onto the next lowest priority. This way, all tasks eventually get a bite of CPU, with high priority tasks getting vastly more than the low priority ones.

Obviously, the initial setup of the lists is critical, and should be done in c_entry:

task_t * __sleep_task;

for (int i = 0; i < 31; i++) {
__priority_lists[i] = (task_list_t *)malloc(sizeof(task_list_t));
SET_CAR(__priority_lists[i], skip);
SET_CDR(__priority_lists[i], nil);
}

__priority_lists[31] = (task_list_t *)malloc(sizeof(task_list_t));
SET_CAR(__priority_lists[31], __sleep_task);
SET_CDR(__priority_lists[31], nil);

The astute amongst you will notice the use of the C library function malloc() in there, despite not having a c library. Don't worry about it. It'll come later. Do worry about me not checking for errors :)

Note that priority 31 has *no* 'skip' entry, and points to a real task. This task should not, under any circumstances, be missed out.

Now that's all done, we can find the next runnable task.

/* lispish function */
task_list_t * nconc(task_list_t * car, task_list_t * cdr) {
if (car == nil) {
return cdr;
} else {
task_list_t * x = car;
while (CAR(x) != nil) x = CAR(x);
SET_CDR(x, cdr);
return car;
}
}

task_t * next_runnable_task() {
for (int i = 0; i < 32; i++) {
while(CAR(__priority_lists[i] != skip)) {
/* rotate the list */
task_list_t * car = CAR(__priority_lists[i]);
task_list_t * cdr = CDR(__priority_lists[i]);
SET_CDR(car, nil);
__priority_lists[i] = nconc(cdr, car);
/* check runnability */
if (car->_car->state == TASK_RUNNABLE)
return car->_car;
}
}
/* we should never get here, but just in case, eh? */
return __sleep_task;
}

Now, that's all fine and well, but what about setting up tasks and actually making them swap? Ah. That's a bit more complex, and we're gonna have to delve down into assembler again. I'll get into that next time round.

Until then, though, here's a couple of little functions we needed before.

void * malloc(size_t size) {

extern char * __heap_top;
extern char * __memtop;
char * prev_heap_top = __heap_top;

if (__heap_top + size > __memtop) {
return (void *)0;
}

__heap_top += size;
return (void *) prev_heap_top;

}

void sys_sleep() {
for(;;){
// ARMv6 Wait For Interrupt (WFI)
uint32_t * reg = 0;
__asm__ __volatile__ ("MCR p15,0,%[t],c7,c0,4" :: [t] "r" (reg));
}
}

Developing a multitasking OS for ARM part 2

2011-12-11T18:08:00.001+01:00

Okay, kids, gather around and we'll carry on where we left off.

Now, we have the ARM booting, jumping to a reset handler, and dropping into an endless loop. That's a pretty good start. But really, we'd like to do something more - well - how to put this - "more".

In order to do this, we need to have a bit more understanding about how the ARM itself works.

If we go to the ARMv7AR Architecture Reference Manual (which can be had by registering at arm.com, or by downloading a hooky copy off the internets, either approach is feasible, and one at least of which is recommended), we see, in section B1 (the System Level Programmer's Model) a certain amount of interesting reading. Forget the "privilege" aspect for the moment, and let's skip ahead to section B1.3.

We find that the processor has 8 separate operating modes. These are:

User Mode, System Mode, Supervisor Mode, Monitor Mode, Abort Mode, Undefined Mode, IRQ Mode, and FIQ Mode

If we look back at the set of vectors we set up earlier, a lot of these "cross over". So when we drop into the IRQ vector, we will be in IRQ mode. FIQ, FIQ mode. Either of the aborts, Abort mode. Undefined instruction, undefined mode, and so on. What's interesting is how the machine registers are shared between modes, and particularly the fact that all but system/user modes have their own stack pointers.

Now, when the ARM starts up, it is in SVC mode. That's the way it is, and you can't change that. And when it starts up, no stack has been defined. So you need to be really damned careful in the first bits of the reset code.

Stacks on the ARM grow downwards, so the best thing to do generally is to put them at the top of memory. As such, a typical reset routine will start by finding out how much memory is available, then setting up stack pointers for each of the operating modes. We're nothing if not typical, so let's look at how we do that.

First thing - sizing memory. On the versatile baseboard as emulated by qemu, this is easy. We try writing to a bit of memory, then read back - if the value is set, there's memory there, if there's not, then we are above the top of memory. It's not quite so simple on the Pi, as trying to write outside of physical RAM will cause an exception. However, we're going to be a bit clever, and try to kill 2 birds with one stone.

Firstly, we need to set up some big fat global variables.

.global __memtop
__memtop: .word 0x00400000 /* Start checking memory from 4MB */
.global __system_ram
__system_ram: .word 0x00000000 /* System memory in MB */
.global __heap_start
__heap_start: .word __bss_end__ /* Start of the dynamic heap */
.global __heap_top
__heap_top: .word __bss_end__ /* Current end of dynamic heap */

__bss_end__ is set up by the linker, and it would be much better of me to use that for the initial value of __memtop (rounded up to the nearest megabyte) as well. But hey, I'm lazy. It'll come back to bite me later, I'm sure.

Now, as the Pi causes an exception on writes outside memory, we need to patch in a handler, temporarily. Here's the handler:

/* temporary data abort handler that sets r4 to zero */

/* this will force the "normal" check to work in the */

/* case (as, I believe, on RasPi) where access 'out */

/* of bounds' causes a page fault */

temp_abort_handler:

mov r4, #0x00000000

sub lr, lr, #0x08

movs pc, lr

Note how the comment indicates I'm not absolutely sure this will work. This is, frankly, because I'm not sure if this will work on a real Pi, and nobody wants to let me get my hands on one. Still, let's pretend, eh?

/* This tries to work out how much memory we have available */

/* Should work on both Pi and qemu targets */

FUNC _size_memory

/* patch in temporary fault handler */

ldr r5, =.Ldaha

ldr r5, [r5]

ldr r6, [r5]

ldr r7, =temp_abort_handler

str r7, [r5]

DMB r12

/* Try and work out how much memory we have */

ldr r0, .Lmemtop

ldr r1, .Lmem_page_size

ldr r1, [r1]

ldr r2, .Lsystem_ram

ldr r3, [r0]

.Lmem_check:

add r3, r3, #0x04

str r3, [r3] /* Try and store a value above current __memtop */

DMB r12 /* Data memory barrier, in case */

ldr r4, [r3] /* Test if it stored */

cmp r3, r4 /* Did it work? */

bne .Lmem_done

ldr r3, [r0]

add r3, r3, r1 /* Add block size onto __memtop and try again */

str r3, [r0]

b .Lmem_check

.Lmem_done:

ldr r3, [r0] /* get final memory size */

lsr r3, #0x14 /* Get number of megabytes */

str r3, [r2] /* And store it */

/* unpatch handlers */

str r6, [r5]

DMB r12

bx lr

.Lmemtop:

.extern __memtop

.word __memtop

.Lmem_page_size:

.extern __mem_page_size

.word __mem_page_size

.Lsystem_ram:

.extern __system_ram

.word __system_ram

.Ldaha:

.extern data_abort_handler_address

.word data_abort_handler_address

We see a few things here. Firstly, how to patch in and out the handler. Also, that I've got fed up with doing the whole .code 32; .global foo; foo: rigmarole and defined a macro called FUNC. We also see a macro called DMB, which implements the ARMv6 Data Memory Barrier (ARMv7 has a 'dmb' instruction, to do that, we don't). For what it's worth, these are the macros:

.macro FUNC name

.text

.code 32

.global \name

\name:

.endm

/* Data memory barrier */

/* pass in a spare register */

.macro DMB reg

mov \reg, #0

mcr p15,0,\reg,c7,c10,5 /* Data memory barrier on ARMv6 */

.endm

So, we can hopefully now find out how much memory we have, with __memtop containing the actual top of memory and __system_ram containing the number of megabytes in case it's useful to know.

So let's look at the start of _reset...

.equ MODE_BITS, 0x1F /* Bit mask for mode bits in CPSR */

.equ USR_MODE, 0x10 /* User mode */

.equ FIQ_MODE, 0x11 /* Fast Interrupt Request mode */

.equ IRQ_MODE, 0x12 /* Interrupt Request mode */

.equ SVC_MODE, 0x13 /* Supervisor mode */

.equ ABT_MODE, 0x17 /* Abort mode */

.equ UND_MODE, 0x1B /* Undefined Instruction mode */

.equ SYS_MODE, 0x1F /* System mode */

FUNC _reset

/* Do any hardware intialisation that absolutely must be done first */

/* No stack set up at this point - be careful */

ldr r0, =.Lsize_memory

ldr r0, [r0]

cmp r0, #0

blxne r0

/* Assume that at this point, __memtop and __system_ram are populated

/* Let's get on with initialising our stacks */

mrs r0, cpsr /* Original PSR value */

ldr r1, __memtop /* Top of memory */

bic r0, r0, #MODE_BITS /* Clear the mode bits */

orr r0, r0, #IRQ_MODE /* Set IRQ mode bits */

msr cpsr_c, r0 /* Change the mode */

mov sp, r1 /* End of IRQ_STACK */

/* Subtract IRQ stack size */

ldr r2, __irq_stack_size

sbc r1, r1, r2

bic r0, r0, #MODE_BITS /* Clear the mode bits */

orr r0, r0, #SYS_MODE /* Set SYS mode bits */

msr cpsr_c, r0 /* Change the mode */

mov sp, r1 /* End of SYS_STACK */

/* Subtract SYS stack size */

ldr r2, __sys_stack_size

sbc r1, r1, r2

bic r0, r0, #MODE_BITS /* Clear the mode bits */

orr r0, r0, #FIQ_MODE /* Set FIQ mode bits */

msr cpsr_c, r0 /* Change the mode */

mov sp, r1 /* End of FIQ_STACK */

/* Subtract FIQ stack size */

ldr r2, __fiq_stack_size

sbc r1, r1, r2

bic r0, r0, #MODE_BITS /* Clear the mode bits */

orr r0, r0, #SVC_MODE /* Set Supervisor mode bits */

msr cpsr_c, r0 /* Change the mode */

mov sp, r1 /* End of stack */

/* And finally subtract Kernel stack size to get final __memtop */

ldr r2, __svc_stack_size

sbc r1, r1, r2

str r1, __memtop

/*-- Leave core in SVC mode ! */

/* Zero the memory in the .bss section. */

mov a2, #0 /* Second arg: fill value */

mov fp, a2 /* Null frame pointer */

ldr a1, .Lbss_start /* First arg: start of memory block */

ldr a3, .Lbss_end

sub a3, a3, a1 /* Third arg: length of block */

bl memset

ldr r2, .Lc_entry /* Let C coder have at initialisation */

mov lr, pc

bx r2

cpsie i /* enable irq */

cpsie f /* and fiq */

/* Initialisation done, sleep */

ldr r2, .Lsleep

mov lr, pc

bx r2

.Lbss_start: .word __bss_start__

.Lbss_end: .word __bss_end__

.Lc_entry: .word c_entry

.Lsleep: .word sys_sleep

Note the use of msr cpsr_c, rx - this is how we change mode. We can change mode this way from any mode except user mode. Luckily, the user mode stack pointer is shared with system mode, so we don't need to drop into user mode at all. So we go off, find how much memory we have, then for certain of the operating modes, we set up a stack pointer. We then use a pre-written implementation of memset() to zero out the bss section, let the 'c' code have a go at initialising its stuff via c_entry(), turn on interrupts, and go to sleep via sys_sleep().

Next up, how we go about doing useful work...

Developing a multitasking OS for ARM part 1

2011-12-07T10:11:00.001+01:00

My Scheme OS for the Raspberry Pi SBC is coming along nicely (code at https://gitorious.org/lambdapi), and a couple of comments on the Raspberry Pi forum kinda kicked me into actually documenting some of the process of what I've been doing. So, here goes.

Firstly, the toolset.

The first thing we'll be needing is development tools. Yeah, there's "off the peg" toolsets available, but I wanted to be up at the bleeding edge. So, off to GNU's site, and let's get cracking.

I built and installed the latest versions of libtools (which includes the assembler and linker), gcc, g++, newlib and gdb, all for target arm-none-eabi. If you want to know how to do this, googling "arm bare metal" should elucidate. Otherwise, there's always codesourcery.

Now, booting. Obviously, the first thing we need to do is boot the board. In my case, it's very uncomplicated. No first-stage booters, no relocating stuff from flash, just a bunch of RAM that your binary gets loaded into, starting at address 0x00000000. Easy peasy.

So. How does ARM (specifically, the ARM1176jzf-s processor on the Raspberry Pi) boot? Well, there's chapter and verse on the ARM site, but here's the TL;DR version.

When the ARM powers on, it executes ARM (32 bit) instructions starting from address 0x00000000.

Simples, right? Well, not quite. Address 0x00000000 is the start of what's known as the exception vector table, which contains 8 bytes for each of 8 potential exceptions. 8 bytes (or 2 words) is enough to store an absolute jump instruction, or an instruction to move an address from memory into the program counter. So the simplest vector table would look like this:

.section .reset
.code 32
.global __reset
__reset:
b _reset @ Power on reset
b _undef @ Undefined instruction
b _swi @ Software interrupt
b _prefetch_abort @ Prefetch Abort
b _data_abort @ Data abort
b . @ Unused
b _irq @ IRQ
b _fiq @ "fast interrupt"

And that would be fine. However, that's not how it's normally done, mainly because it's impossible, with this setup, to change the vectors on the fly. So what we do is this:

.section .reset, "ax"
.code 32
.global __reset
__reset:
ldr pc, _reset_address
ldr pc, _undef_address
ldr pc, _swi_address
ldr pc, _prefetch_abort_address
ldr pc, _data_abort_address
b .
ldr pc, _irq_address
.global _fiq
_fiq:
@ Fast interrupt handler starts here
b _no_handler

.global _no_handler
_no_handler:
b _no_handler

_reset_address: .word _reset
_undef_address: .word _undef
_swi_address: .word _swi
_prefetch_abort_address: .word _prefetch_abort
_data_abort_address: .word _data_abort
_irq_address: .word _irq

.global _reset_address
.global _undef_address
.global _swi_address
.global _prefetch_abort_address
.global _data_abort_address
.global _irq_address

.weak _undef

.set _undef, _no_handler

.weak _prefetch_abort

.set _prefetch_abort, _no_handler

.weak _data_abort

.set _data_abort, _no_handler

.global _reset

_reset:

b _no_handler

.global _swi

_swi:

b _no_handler

.global _irq

_irq:

b _no_handler

That's loads bigger, but what does it change, exactly?

The "fast interrupt" code gets to miss an indirection, so it's faster. We simply start the interrupt handler directly at the end of the vector table. I'm not actually doing this at the moment, but it's possible.

The other exceptions load their address from an indirection table, so we can repatch them on the fly.

We have a "generic" handler for unhandled exceptions. The way that gets patched in is to do with the linker. A .weak directive for a symbol will allow us to simply not define a symbol in our code, and the linker will replace it with zero instead of barfing. The .set directive enables us to use a different default to zero. Thus, any of the _undef, _prefetch_abort or _data_abort entry points (in the code above) will redirect to _no_handler unless we define those entry points elsewhere. This is a trick we'll use again later. Note _reset, _swi and _irq have no defaults, and thus must be defined elsewhere (I've defined them to simply jump to _no_handler for the moment.

All we need to do is assemble that and link it to load at 0x00000000, and we have a booter. It will do bugger all, but it will work.

Garbage collection for an SD/MMC-based persistent store

2011-10-19T21:29:00.000+02:00

My Lisp/Scheme based OS is moving on apace. I've actually got a basic OS running on STM32, but it's feeling a bit cramped, and there's a new game in town - Raspberry Pi. Raspberry Pi (or, to shorten it a bit, RasPi) is a credit-card sized ARM11 based machine intended for educational use. And it's cheap. Really, really, cheap. there's a few oddities to it; it's actually based on a Broadcom SoC that's, in reality, a top whack GPU with a sorta old-hat ARM core bolted on as a bit of an afterthought. As such, it boots "oddly", GPU first and then ARM, but hey. The board itself has no onboard flash; persistent storage is SD card only (or, I guess, USB mass storage).

As could probably be guessed, it's coming with Linux on board, but hey, who cares about Linux?

Never one to make things easy on myself, I've expanded the scope of my OS. The Lisp/Scheme core is still there, the concept of syscalls as closures, all that good stuff. But I keep coming back to the Newton. Ah, my beloved NewtonOS. A totally persistent OS, one that takes power failures and years sitting in a drawer in its stride, a system where you whack new batteries in and you're back exactly where you were almost the moment you've let go of the power toggle switch. This is exactly what Stanislav is talking about in his third law of sane computing.

So. Persistence, then. How's that gonna work?

Before we start, I should note that the following technical stuff is nothing to do with wear levelling (which task is carried out quite adequately by the onboard controller of the SD card).

We have a quantity of RAM (256MB in the case of the Pi) which we want to use as a read / write cache for a larger quantity of persistent storage. In this case, Flash memory accessed through an SD/MMC card interface.

We could take a naïve approach, and simply page stuff in and out, but there is a significant performance overhead, particularly with flash memory. Not only are writes to flash slow, but you can only write to a block once, and then it needs to be erased before you write again. And erasing is really slow.

Any given SD card is split into a number of sectors (typically between 512 bytes and 2K long). A sector is the smallest unit we can read. Those sectors are grouped into erase groups (typically in the 128KB - 2MB range). An erase group is the smallest unit we can erase. We can write to a sector, but if we try to write to it twice, the entire erase group has to be erased and the old contents (plus the new contents of our sector) written back. This is a positively glacial operation.

If we take a sane approach, we block everything at the erase group size, and control when (and how) we write back to the card. If we take the approach of writing data back to a different erase group, we can put off the pain of erasing the old one, and do it at our (or the card's) leisure.

Now, as we don't know exactly where an erase group will be paged into memory (and we can't restrict it to a specific location, as the card storage is potentially bigger than real memory), we have to use an indirect addressing method, using a "logical erase group number" (which can't be the actual erase group number, as that will change underneath us) and an index or address into the block of memory. This adds some overhead to pointer dereferencing, of course, but it's mainly done using shifts and masks; dropping to assembler to do this should make it at least tolerable.

The bigger pain is garbage collection. Lisp and Scheme are garbage collected languages, and we need a garbage collector that doesn't hurt us.

At this point, I should probably set out some requirements for garbage collection:

It should reclaim as much memory as possible (duh)
It should not require paging in gigabytes of memory (that costs potentially enormous amounts of time).
It should never (if possible) force data to be written back to storage (which would be worse than paging in).
It should (if possible) be concurrent with application usage.
It should have a bounded worst case time per cycle (Java, I'm looking at you)

A traditional garbage collector is gonna hurt us plenty. Why is that?

The way most garbage collectors work is by tracing from a group of accessible objects to find all objects in the heap that are addressable. These addressable objects are then copied somewhere "safe", and the rest thrown away. That's pretty much the gist of it (there are various complications, but the reader is referred to the relevant literature for further detail).

Now, that whole "copying" thing means that, for every garbage collection cycle, the erase group(s) containing the "live" objects will have to be written back to the SD card, whether the objects themselves have changed or not. Ouch.

But surely, you say, there exists a way of collecting garbage without moving objects around? As it happens, dear reader, there does. H.G. Baker's "Treadmill" non-copying garbage collector is a particularly good (and easy to code) example. It comes with a certain amount of hurt itself, but it gets rid of the copying requirement, and that's a good start.

The main hurt of Baker's treadmill is the requirement to hold every object in a doubly-linked list. For a lisp implementation where objects generally look like this:

struct cell {
uint32_t car;
uint32_t cdr;
};

adding in the doubly-linked list produces this, which has twice the storage requirement:

struct cell {
struct cell * next;
struct cell * prev;
uint32_t car;
uint32_t cdr;
};

Ouch, again. But hey, memory's cheap, and we're doing this in order to use RAM as a window on the bigger, persistent store - not really an issue. It should be noted that the structure above is only indicative; the links don't need to be persisted and can be kept separate of the actual cell contents. The overhead, of course, remains the same.

The other hurt is not to do with Baker's algorithm, but is more general - GC tends to want to access all your heap. And when your heap is feasibly orders of magnitude larger than real memory, that's gonna cause a load of thrashing.

So I started with the idea of not GCing non-swapped-in erase groups. Do your garbage collection on what you have in memory at the time, don't try and pull in any non-swapped-in erase blocks, and leave it at that - the other erase groups will get GCed when they eventually get swapped back in. Great, said I, coded about half of it up, and went to bed. And then woke up in the middle of the night.

"What about objects in a swapped in erase group which are only pointed to by objects in erase groups that are not swapped in? How the hell do I distinguish them from free objects if I don't know where they come from, or even that they are being pointed to?"

Ah, tits!

Yep, if we're doing things in a naive way, but not swapping in every erase group as we traverse, we're gonna lose objects, and corrupt structures that are partially swapped in.

We need to get clever.

Firstly, let's stick with the idea of erase groups, and not garbage collecting the "world". Indeed, let's not even try collecting our entire heap, we can restrict ourselves to a single erase group, or even a single sector if we like. All we have to do is decide not to follow links outside the (relatively) little block of memory we're looking at. We take our set of system roots, for every one that's in our block, we trace its links until we get to leaves or a link outside the block. The rest is totally normal as per Baker's algorithm.

By restricting ourselves to a single block of memory, we can obviate the need to have a full doubly-linked list for our entire heap; all we need is a doubly linked list for the block we're currently collecting, and that can be generated trivially at the beginning of the GC. This buggers the simplicity of allocating under Baker (which is a dereference and pointer increment), but rather than holding a full list all we need to hold is a bitmap.

Still, that hasn't solved the issue of links into our collected block.

As it turns out, the solution to that is incredibly simple, and falls back to one of the oldest forms of garbage collection - reference counting. Along with our cell data, we carry a reference count variable, which counts the number of times a cell is referenced by cells outside the block. This looks a bit like this:

struct cell {
uint32_t car;
uint32_t cdr;
uint16_t refcount;
};

If we create a cross-block link, we increment the reference count, if we destroy one (either by explicitly removing the link in code, or by freeing the referencing object during a garbage collection), we decrement it. As part of building our list of root objects, we scan the block for those objects with a non-zero refcount, and push those direct into the list of roots.

Now, maintaining refcounts is a pain in the ass, but with the granularity of allocation blocks we're talking about here (between 128KB and 2MB, remember), the number of cross-block references are liable to be very small. We can help this by preferring allocation of new objects in the block their "owner" inhabits (which will also help reduce object scattering, and thus paging issues).

So. what does the solution look like?

Firstly, we have some basic types:

typedef struct cell {
uint32_t car;
uint32_t cdr;
} cell_t;

typedef struct reference_count {
uint16_t colour:1; // indicator for gc, see Baker
uint16_t count:15;
} reference_count_t;

Some calculations:

// Every erase group must store :
// n cells (8 bytes each), n refcounts (2 bytes each)
// and n / 32 free cell bitmaps (4 bytes each)
#define CELLS_PER_BLOCK (erase_group_size * 8) / (64 + 16 + 1)

Therefore cell storage within an erase group looks like this (it's not actually defined like this, as CELLS_PER_BLOCK is dynamically calculated based on actual card characteristics):

cell_t cells[CELLS_PER_BLOCK];
reference_count_t refcounts[CELLS_PER_BLOCK];
uint8_t bitmaps[CELLS_PER_BLOCK];

The garbage collection algorithm is thus (using a single, transient, doubly linked list for CELLS_PER_BLOCK elements) :

- For each cell in the erase group
- if cell is in set of root objects, or has a refcount != 0, add to "grey" objects
- else add to "ecru" objects
- Do Baker's treadmill algorithm, restricting ourselves to intra-block links
- For each free object
- set "free" indicator in bitmaps
- if object has extra-group link(s)
- decrement refcount(s) on externally referenced groups (may require paging)
- reinitialize to NIL . NIL or similar
- flag group as "dirty"

And that's about it. Allocating involves finding a free cell in the relevant erase group (made relatively easy using ARM's CLZ operator), assignment has to check for cross-erase-group links.

Note that the only time garbage collection will require the erase group to be flushed back to storage is in the (rare) case where we free a cell that has extra-group links. The "free" bitmap may be out of date on loading a group from flash, but it will never indicate that a non-free cell is free (allocation of a cell will update the bitmap to indicate the non-free status of that cell, and require a flush). The bitmap will be updated on the first gc cycle for the group, at which point it should be up-to-date.

As an added bonus, as long as everything is persisted, suspending a process is simply a case of incrementing the reference counts of all its root objects and stopping the process. Starting it again is decrementing those counts, and you're back to exactly where you were.

How d'ya like them apples?

TiVo^H^H^H^HAndroidization

2010-12-17T18:01:00.000+01:00

A few years back there was a big hoo-hah in the open source world, and it was at least partially responsible for the creation of the GPLv3. That hoo-hah was the TiVoization of the Linux kernel.

In short, what happened was this:

TiVo, inc. created their famous PVR device, which took the world (especially the geek world) by storm. At the heart of the device was a bunch of GPL software, including the Linux kernel. This later fact was, IMO, a large part of why TiVo took the geek world by storm, but that's another argument.

TiVo did what any good company using GPLed software should do - they delivered the source of their modifications to the GPLed software, and kept their non-GPLed software scrupulously away from the GPLed stuff.

So far, so good, right? Wrong.

Whilst it was possible for anyone to recompile their own version of the TiVo firmware, it was not possible to flash that recompiled firmware onto a TiVo branded device. The firmware images used to flash the TiVo were cryptographically signed, and the means to do that was not public. There were, of course, good reasons for this, not least of which was that the media companies would have, legally speaking, shat upon TiVo, inc. from a great height if it were not so.

There was much oohing and aahing from the GPL advocates over this, and it was generally decided that this was somehow wrong, and it was going to kill the GPL, and other such crap. And thus was born the GPLv3, which "protected" not only the software, but also the hardware it was designed to run on. Linus and the other kernel developers, who saw little wrong with what TiVo had done, decided to stick with the old GPLv2 anyway, and to hell with V3.

Fast forward a few years. The Linux kernel has not died. The GPL has not died. But now there is a threat to the GPL, and it is attacking both v2 and v3. It's a real and present danger, and it's being ignored (at best) or cheered on (at worst). That threat has a name. Its name is Android.

It's not Android as such that is the threat, but the market in which it is being used - mobile devices. An open system is anæthema to the hermetically closed world of mobile phones and telecoms carriers. Android is being claimed as the saviour of the open source world from the big bad ogres at Apple and MS. I believe this claim is wrong.

Even Google aren't being the open source heros they are claimed. The (non-GPL parts of the) source for Android 4.x (Ice Cream Sandwich) was released months after the first devices hit the street, and I'm not sure if the 3.x series has ever been made public.

Telephony providers are absolutely against people reflashing their devices (or even rooting them), and many mobiles are every bit as TiVoised as the original TiVo. And that inability to reflash is being used as a marketing device by the providers / manufacturers. "Benefit from Android x.x", they trumpet, "get yourself a new contract with handset / tablet X.1", quietly ignoring the fact that handset / tablet X.0 could quite happily run Android x.x should they bother to take a little time to provide a firmware upgrade. And yet Apple are "evil", and "push you to consume", although they have a policy of supporting hardware for a decent amount of time. No, Apple are evil because they are "closed source", and to avoid that we'll happily get fucked up the arse by someone waving a GPL banner.

But the worst, the absolute worst, of the lot, are the Chinese manufacturers of cheap Android enabled devices, motherboards, and chipsets. It is absolutely impossible to get them to release the slightest piece of source code, despite the fact they are obliged to do so.

Android is nothing more than a system for pushing ads to your mobile device. It's nothing to do with freedom, unless you're talking about Google's freedom to rape your private data. The telephony providers are using it because it costs them jack shit. Nothing to do with consumer benefit, nothing to do with freedom, simple bottom line accounting. The Chinese manufacturers are using it for the same reason, and because MS have got harder on hooky copies of WinCE.

None of them give a flying fuck about "freedom", but between them, they may bring the GPL down.

How good is your hashing?

2010-12-17T14:41:00.000+01:00

As promised in my last post, I'm working on an embedded lisp-based OS. Yeah, another one. Because what the world really needs is yet another geek's idea of what an OS should look like.

Well, fuck the world, I'm scratching an itch.

Now, if I were being sensible, I'd target something usable, like my Wits A81 tablet device. A little lispy tablet could be really neat (and, indeed, it may well end up being so). However, I decided to start a bit smaller.

A lot smaller, actually.

Yep, a lisp-based OS on a microcontroller. Not, I might add, the st8ms this blog originally started with (and is titled as), but it's bigger brother, the stm32. It's an ARM Cortex-M3 processor, and the one I have in hand has 128K of flash and 8K of RAM, which is quite nifty.

Now, anything that's gonna fit into that little space is gonna have to be tight. Sure, I can push as much code as possible into flash and execute from there, but that 8K is a really tight limit for something like a Lisp, even a cut down one. And so, I started thinking about what takes up lots of space in lisp.

Firstly, there's objects. A naive implementation of boxed objects in Lisp means that even the humblest character takes up a significant amount of space, with 24 bytes not being unheard-of. Well, bollocks to that. I'm being as tight as I can.

Once you've squeezed stuff like characters and numbers and so on down, though, you start looking at what you can get shot of. Symbols, for example. They are used as unique identifiers, and ar generally stored as a hash value and a literal string. Now, the hash value is what's used most of the time, and the string is only really used when "exploding" the symbol out into an array of characters. So if I'm willing not to do that, I can get away with *just* holding the hash. That's a significant saving.

So. What hash to use?

I need something that can be pushed into a single word of space (4 bytes), and which will allow me to detect collisions. By which I mean that if "a" and "b" resolve to the same hash value, I need to be able to tell. The first bit is easy enough, but the second is hard as nails

A google for hashing algorithms will generally end up pointing you to Dan Bernstein's venerable djb2. Unfortunately, it's not really very good, and it certainly doesn't handle the second case. For that, what I need is an algorithm that pushes out *two* hash values, a primary and a secondary.

Enter Bob Jenkins' 'lookup3.c', particularly 'hashlittle2()'. This is a rather nice hashing algorithm that throws out a pair of hash values, has very good characteristics, and runs fast.

But, oh noes! Compiling it for the STM32 results in over 1K of code. Surely we can do better than that? Yes, we can.

.global hash
.type   hash, %function
.align 2
@ Hash Function
@ Thumb-2 implementation of 'hashlittle2' by Bob Jenkins.
@ In :  R0 -> pointer to string
@       R1 -> length of string
@       R2 -> Initial value for 'hash c'
@       R3 -> Initial value for 'hash b'
@ Out : R0 -> 'hash c', the main hash value
@       R1 -> 'hash b', the secondary hash value
@ Clobbers R2, R3, flags 
hash:   push    {r4-r7,lr}
        @ Within the function, we use registers as follows:
        @ r1    : length
        @ r2-r4 : temporary for character loading
        @ r5-r7 : a, b, c
        
        @ initial setup
        adr     r7, hash_constant @ a = b = c = 0xdeadbeef + length + hash c
        ldr     r7, [r7]
        adds    r7, r1
        adds    r7, r2
        mov     r5, r7
        mov     r6, r7
        adds    r7, r3          @ c += hash b
        
hash_loop:
        cmp     r1, #0x0c       @ Is r4 <= 12?
        it      le
        ble     hash_tail       @ If so, go do the tail part
        
        ldmia   r0!, {r2, r3, r4}       @ Load values
        adds    r5, r2
        adds    r6, r3
        adds    r7, r4
        subs    r1, #0x0c       @ Subtract 12 from length
        
        @ Mix
        subs    r5, r7                  @ a -= c
        eor.W   r5, r5, r7, ror #28     @ a ^= rot(c,4)
        adds    r7, r6                  @ c += b
        
        subs    r6, r5                  @ b -= a
        eor.W   r6, r6, r5, ror #26             @ b ^= rot(a,6)
        adds    r5, r7                  @ a += c;
        
        subs    r7, r6                  @ c -= b;  
        eor.W   r7, r7, r6, ror #24     @ c ^= rot(b, 8);  
        adds    r6, r5                  @ b += a;
        
        subs    r5, r7                  @ a -= c
        eor.W   r5, r5, r7, ror #16     @ a ^= rot(c,16)
        adds    r7, r6                  @ c += b
        
        subs    r6, r5                  @ b -= a
        eor.W   r6, r6, r5, ror #13             @ b ^= rot(a,19)
        adds    r5, r7                  @ a += c;
        
        subs    r7, r6                  @ c -= b;  
        eor.W   r7, r7, r6, ror #28     @ c ^= rot(b, 4);  
        adds    r6, r5                  @ b += a;       
        
        b       hash_loop
hash_tail:
        cbz     r1, hash_done           @ length 0 requires no extra work
        
        ldmia   r0!, {r2, r3, r4}       @ Load values
        adr     r0, do_hash_mask
        add     r0, r0, r1, lsl #2
        
do_hash_mask:
        mov.W   pc, r0                  @ doubles for count 0 entry in masking table, *must* be 4 bytes hence .W
        @ Here we mask off the bits we don't want according to 
        @ what data we have
        bic     r2, #0x0000ff00         @ count is 1, mask off all but least significant byte
        bic     r2, #0x00ff0000         @ etc etc
        bic     r2, #0xff000000 
        bic     r3, #0x000000ff
        bic     r3, #0x0000ff00
        bic     r3, #0x00ff0000
        bic     r3, #0xff000000
        bic     r4, #0x000000ff
        bic     r4, #0x0000ff00
        bic     r4, #0x00ff0000
        bic     r4, #0xff000000
        bic     r4, #0x00000000

        adds    r5, r2                  @ Add masked vales before final mix
        adds    r6, r3
        adds    r7, r4
        
        @ Final mix
        eors    r7, r6                  @ c ^= b
        sub     r7, r7, r6, ror #18     @ c -= rot(b,14)
        eors    r5, r7                  @ a ^= c
        sub     r5, r5, r7, ror #21     @ c -= rot(c,11)
        eors    r6, r5                  @ b ^= a
        sub     r6, r6, r5, ror #7      @ b -= rot(a,25)
        eors    r7, r6                  @ c ^= b
        sub     r7, r7, r6, ror #16     @ c -= rot(b,16)
        eors    r5, r7                  @ a ^= c
        sub     r5, r5, r7, ror #28     @ c -= rot(c,4)
        eors    r6, r5                  @ b ^= a
        sub     r6, r6, r5, ror #18     @ b -= rot(a,14)
        eors    r7, r6                  @ c ^= b
        sub     r7, r7, r6, ror #8      @ c -= rot(b,24)
        
hash_done:
        mov     r0, r7
        mov     r1, r6
        pop     {r4-r7, pc}

hash_constant:
        .word   0xdeadbeef

.ltorg

There you go. 206 bytes of hash function. There's probably a few bytes to shave off here and there, but it works pretty well.

As it happens, I'm only using 30 bits of the main hash, with the lowest 2 bits being used to indicate type, in order that symbols fit completely into a single machine word.

All modern operating systems are shite.

2010-10-29T12:45:00.001+02:00

"Modern" operating systems are, to my eyes, fundamentally broken. Indeed, there's very little that's "modern" about them, when it comes down to it.

They are seemingly all mired in the concept of being nothing more than a layer over hardware, something that allows single-purpose "applications" to access that hardware in a consistent manner. The focus is wholeheartedly on the applications, and not on the data those applications use.

Admittedly, some of those systems are better than others. Apple's OSX is nice enough to use, mainly because it's decent enough to get out of the way when you need it to. But even so, it's conceptually no different to Microsoft's Win7, or even Vista, XP, Win2K (go back down the MS lineage as far as you want here) or any other "desktop" operating system - the only real distinguishing factor apart from what applications are compatible is how you get on with the UI. Personally, I find OSX tolerable, and Windows execrable, but that's personal preference, and not really much different to preferring a Ford over a Fiat.

Even the handheld market, one which was all-but invented by Apples ground-breaking Newton, has taken masive steps backwards from the beauty and simplicity of Newton, or even the sparse functionalism of Palm; "handheld devices", say Jobs, Brin and Ballmer, "are for consumption of pre-rendered media". Forget using them as extensions of your computing environment, forget using them for anything useful (except, perhaps, as a poor replacement for a spirit level), they're there as status symbol, toy, and above all, conduit for advertising.

Yeah, I keep coming back to the Newton. Funny, that.

So, anyway, whilst fiddling with Android, and trying to make mobile devices actually useful again, and generally buggering about with my Wits A81, I've been doing a fair amount of thinking about this. And, indeed, I've been thinking about going further than that, and actually doing something about it.

I started by thinking that something could be done by using the linux kernel as a starting point. After all, it's already developed, and it runs everywhere - why bother reinventing the wheel? Just make a performant "shim" OS over the top of it, and a file system that does what you want, and you're laughing.

But that's suboptimal. Linux (the kernel) is tied to the Unix concept that "everything is a file". Which is a nice enough abstraction, but it doesn't work for me. The reason it doesn't work for me is that "a file" is far from being a rich enough concept. Part of this is to do with metadata (or, more particularly, the lack of it) - it's very difficult to implement interesting inter-application behaviour without metadata and (even more importantly) transparent, dynamic, access methods for that data and metadata.

As an example, let's consider Apple's OSX, and the interaction between AddressBook.app, Mail.app and iCal.app. This is, pretty much, state of the (current) art - you send me an email suggesting a lunch date tomorrow at midday, I double click on the "midday" text and get a "lunch" appointment added to my calendar with you as an "attendee". Pretty damn slick. But all that interaction knows about is those 3 apps - it's hard-coded to only work between those three. This is because the processing is contained in the aplications, and not "owned" by the data. I can't make MyFunkyApp.app do this without linking to a bunch of Apple-provided frameworks (and even then, it's hard, as a lot of the behaviour is not externally exposed), and even when I do, Mail.app doesn't suddenly inherit the ability to do what MyFunkyApp.app does - the interaction only goes one way.

We shouldn't be living in a world where metadata and behaviour is application specific. Developers should be developing behaviour, interfaces and transforms for specific data types, not reinventing the "application" over and over. Users should be able to edit an image directly in an email, and send it back to the sender, without having to save it, open it in anoother application, edit it there, save it again, then send it back. Data should be automatically versioned. It should follow you around. Your mobile device should be an extension of your desktop, able to take important data with you and merge changes back when you return, able to contact your machine over the 'net and fetch data you "forgot". And so on.

Desktop computing hasn't advanced that much since 1984. There have been a few attempts to make things better, but they have, by and large, failed, at least if we measure success in a commercial sense. Newton was one of these. Computing has failed on several of its promises. We are slaves to the machine, not the other way around.

It is clear to me, at least, that we need a change. And the idea has been buzzing around my head for some time. I had considered that much of this could be accomplished by layering something over the Linux kernel, with a metadata-storing file system backing everything up. The problem with this approach is that the two worlds can never be allowed to collide - Linux provides a hardware abstraction layer and nothing else. Everything else the kernel does, including scheduling, would be surplus to requirements. So why not, I thought to myself, develop an OS directly "on the metal" in a dynamic language, do it all from the ground up? After all, it's been done before. The Jupiter Ace was a "home micro" which was coded purely in FORTH. The Symbolics Lisp Machines were coded, from the ground up, in Lisp.

And that hooked me. I've always loved Lisp. It has a beauty which is transcendental, a purity of purpose which is unrivalled in any (non-Lisp) language that's come since. A lot of people get scared by the syntax, but then people get scared by the fact Objective-C uses square brackets and colons, so fuck 'em. Result - I started looking at Lisp-based OSes, to see if it had all been done before. And I found this:

Closos

Now, this started to tickle my interest. Not only was I not insane (or, at least, not insane and alone), but Mikel is one of the original guys on the Newton (and pre-Newton) project at Apple. One of the guys who worked on SK8 at Apple. An insanely talented guy, who seemingly thinks much the same way as I do. Sure, it's not much further advanced than I am, but it at least shows I'm (possibly) not utterly wrong.

So, I'm not mad. And I *am* gonna do this. Stop thinking, start acting.

OpenEmbedded under OSX.

2010-07-31T09:56:00.001+02:00

So, as a result of getting the little android tablet I mentioned before, I've been playing with OpenEmbedded. Unfortunately (for me), it's not supported (or at least not fully) under OSX - even getting the native tools up and running is painful. There's a *load* of gnu-isms in the source, which break strict POSIX compliance, and frankly make it a massive pain to get stuff working.

Much of this can be got around by using precompiled stuff (either pulled from one of the OSX package repositories, fink etc, or, in my case, compiled manually), and then explicitly removed from the OE build system using ASSUME_PROVIDED.

This doesn't fix a few overall issues, though, much of which comes from OE assuming it's built on a system that uses ELF as its binary format.

A large part of this can be fixed with one patch, which I've attached here. $OEBASE/$CHECKOUT/classes/relocatable.bbclass tries to fix up the rpath in any binaries having it, but simply assumes all binaries are ELF format. Obviously, this crashes and burns horribly under OSX, where the runtime format for native binaries is Mach-O. Patch below, apply from $OEBASE/$CHECKOUT with patch -p1


diff --git a/classes/relocatable.bbclass b/classes/relocatable.bbclass
index 2af3a7a..3a4c119 100644
--- a/classes/relocatable.bbclass
+++ b/classes/relocatable.bbclass
@@ -3,6 +3,19 @@ SYSROOT_PREPROCESS_FUNCS += "relocatable_binaries_preprocess"
CHRPATH_BIN ?= "chrpath"
PREPROCESS_RELOCATE_DIRS ?= ""

+def is_elf_file (fullpath):
+    import subprocess as sub
+   
+    p = sub.Popen(['file', '-b', fullpath],stdout=sub.PIPE,stderr=sub.PIPE)
+    err, out = p.communicate()
+    if p.returncode != 0:
+        return 0
+   
+    if out.startswith('ELF'):
+        return 1
+    else:
+        return 0
+       
def process_dir (directory, d):
    import subprocess as sub
    import stat
@@ -24,7 +37,8 @@ def process_dir (directory, d):

        if os.path.isdir(fpath):
            process_dir(fpath, d)
-        else:
+        if is_elf_file(fpath) == 1:
+            # only try to relocate ELF files
            #bb.note("Testing %s for relocatability" % fpath)

            # We need read and write permissions for chrpath, if we don't have
@@ -85,7 +99,7 @@ def rpath_replace (path, d):
    bindirs = bb.data.expand("${bindir} ${sbindir} ${base_sbindir} ${base_bindir} ${libdir} ${base_libdir} ${PREPROCESS_RELOCATE_DIRS}", d).split()

    for bindir in bindirs:
-        #bb.note ("Processing directory " + bindir)
+        bb.note ("Processing directory " + bindir)
        directory = path + "/" + bindir
        process_dir (directory, d)

I'll post more in a little while, including full instructions on getting oe up and running under OSX, but I'm off on holiday for a week.

Android on tablets, rights and wrongs

2010-07-11T10:03:00.000+02:00

This is likely to be a relatively contentious post. I've spent a bit of time trying to get to like Android, and, in short, I can't do it. I don't like Android. I'm sure it's OK as a smartphone OS, but on a tablet, it simply doesn't work for me.

Now, I'm aware that I'm probably not the average user, but I'm (humbly enough) pretty well attuned to what people need to make computers work. That comes from 20+ years in "the biz", using pretty much every operating system there's ever been, including some real wierdos that most people haven't even heard of.

Now, to start hammering on what Android's got wrong, we really need to look at a comparable system that's got it *right*. And it needs to be something I have near me, so out comes the trusty Newton. Yep, that's right. The Newton. A 13 year old, underpowered "pocketable" that was ridiculed in its earlier incarnations for its pisspoor handwriting recognition. Android's gotta be better than that, right? Read on for a load of words on why I think the way I do, but the executive summary is "No, wrong".

Philosophy

Before we get to the "nitty gritty" of little things, we need to look at the design rationales of the systems, or, for want of a better phrase, their "philosophy".

Newton came from a real intention to make a computer that was different, that was better. A radical shift from the 100lb hulking monoliths that lived on or under our desks at the time. A powerful computer that could be dropped into your pocket. A computer that anyone could use. A computer that didn't need a keyboard. It may have been a commercial failure (it cost Apple a lot of money at a time it couldn't afford it), but opened a whole range of new business markets and the whole concept of a pocketable "real computer" made a lot of money for other people.

Android comes from Google. In short, it can be summed up as a device for getting more eyes to Google's primary business, i.e. advertising. Google want to hit a new market (originally smartphones), so they leverage a bunch of open source software and try to make something that looks like what the current market leader (iPhone, in this case) looks like, and dump out a beta. Being "open" means that the hardware manufacturers can make it work on their chips, being free means that the carriers don't have to pay license fees, and being free means the consumer gets a cheaper device. Everyone wins, right? Well, in reality, not quite. Hardware manufacturers have mainly made *one* version work for *one* generation of chips, and have often not lived up to the GPL requirements so that their initial work could be carried on by the public. Carriers couldn't care less about updates, because they'd rather sell you a new phone with a new contract, and realistically, it's hardware costs that drive the pricepoint anyway. Net result is a messy market with a ~33/33/33 split of the 3 current major versions of Android, and most platforms not being upgradeable.

Then along came iPad, and with it a sudden rush of android-running tablets. Because a tablet is just like a scaled-up smartphone, right? Again, "No, wrong".

The problem here, I think, is that Android doesn't really fit in with the use case for a tablet device, and particularly not for the pocketable type of tablet. At least, not for *my* use case, but it's my post so I'll stick with my requirements, thank you very much. The iPad succeeds because it's a tightly controlled device with a tightly controlled market, aiming at consumption of media. It's not a general purpose computer, really - apps live in their own little walled gardens, and you can't run what you want on it. It's a fucking good little gadget, though.

Android thinks it's a phone. Except when it thinks it's an iPad. it dosn't have the same overall control that the iPad/iPhone has, and where Google have tried to enforce certain hardware requirements, they often don't make sense (for a phone *or* for a tablet) except when you look at it from an advertising pusher's point of view. I mean, really, why does a phone, or a tablet, need a GPS? Sure, it might be useful, but I fail to see the absolute necessity. Why restrict to a specific set of screen sizes? Why must it have a camera? After all, anyone who cares about the photos they take won't be using a phone camera anyway. but I digress slightly.

To sum it up: IMO, android is a "me too" iPhone/iPad clone, and not a very good one. It suffers from Google's "permanent beta" mania. Get it out fast and dirty, and fuck the early adopters.

User interface

The overall user interface of Newton is *tight*. It's intended to be used with a stylus, although most selections can be made with a finger. Here's what it looks like, more or less (in reality, it's a lot more "green"):

What we see at the bottom of these two screens is the stuff that's always available, viz: a "menu bar" for the current application, and a "Dock" (to use OSX terminology) for a few common apps and functions (undo, find, assist, more on these later). That uses up a fair amount of available screen space, but the rest belongs to your app. What's important here is that the interface is consistent. From the supplied calendar application to 3rd party web browser, you always know where to go.

Here's another one, with an "add-on" backdrop, and rotated into landscape mode (the green is a little overbearing, probably as it was pulled from an emulator)

The little star at the top of the screen is the "notification" icon for Newton. What Android mainly uses its waste of space "status bar" for.

Android is chaotic. It's mainly intended to be used with a finger, but that doesn't always work. One app might grab full screen and require some sort of gesture to pull up menus, another leaves menus and stuff on screen. Mostly apps leave the status bar at the top of the screen, but it's pretty much a waste of space - there's very little you can do with it. Admittedly, most apps respond to the "menu" button, but not all devices have a hardware menu button. Menu widgets don't seem to be standardised, and some are so small as to be unselectable without using a stylus. If nothing else, it's more food for the "open source can't do UIs" crowd.

Scrolling is standardised on both platforms - on Newton you use the up-down arrow keys, on Android you "swipe". I find that my swipes are taken as clicks or some other UI action about 50% of the time, and although the "inertial" scrolling thing looks cool initially, it's intensely frustrating as your swipe goes that bit too far and zooms waaaaaaaay past what you were looking for.

Closing apps is more or less standardised - the Newt has a little X at the bottom left corner, that closes your app. Android recognises the "back" and "home" buttons, but, again, not all devices have them.

Rotation hits some little glitches, as well. Android assumes you have an accelerometer, and auto-rotates the screen to fit. That's nice, as long as you have an accelerometer. I don't, and there doesn't seem to be any standard "rotate" widget as per the Newton. Which is not to say that the Newt is perfect in this respect, some apps behave very badly when rotated. I would argue, however, that Android should at least provide a widget as a sop to those who don't have an accelerometer.

Finding your data

Newton has a "find" button. It works. It always works. 'nuff said.

Android has a filesystem. A filesystem that you can't access without some sort of file browser. I have 3 on my device already - one works for one thing, one works better for another, and so on. Gah. I don't want to fuck about with filesystems, dammit!

Otherwise, you must find your data from within the application you want to use. Interfaces vary. It's messy. It's inconsistent.

This reveals another philosophical thing. Newton doesn't have a "filesystem" as such. No hierarchy, no structure. A big searchable "soup" of data and applications. Everything is data, everything has a bunch of attributes, you can search it. It's a database. While this is somewhat shocking to those used to the current way of doing things, it's hardly new : "Pick" did this in the 60s, BeOS did this to a certain extent, so did Apple to a very limited extent with the "classic" MacOS (and also with OSX).

The current "hierarchical" way of doing things is massively backwards, and it's holding us back. We use the name and location of a file to indicate its metadata. This makes no sense (as, for example, those who've been hit with Windows-based trojans and email viruses can testify). It works for certain system-level applications, but for user data manpulation, it's utter pants.

Currently, this need is covered to a certain extent inside individual applications (think, for example, iTunes), but that data can't be easily shared to other apps without intrinsic knowledge of how to "get at" the database, and upgrades to one app often break other stuff further down the chain.

It would be much nicer to simply have something where you could query aong the lines of "show me all the emails I sent to fred over the last month, sorted by date". "Okay, now show me the emails in that list which had attachments". "Now show me the attachments which pertained to project 'foo'". Etc etc.

It's about time someone came up with a filesystem that is completely non-hierarchical (I'm currently working on a fusefs that does exactly this, actually).

App launching

On the Newton, click on the "extras" button, go to the tab for stuff *you* have classified as applications, click your app. Or use "find". Or click on an associated piece of data. Or you might use "Assist".

On Android, go back to the home screen, go to the right tab, click your app.

To me, the whole "application centric" way of doing things smacks of "desktop computing metaphor crammed into a handheld device" with little thought. But maybe that's just me.

Data input

With Newton, you write on the screen. That's pretty much it. Really. Just write directly in the boxes. Newton usually turns it into a textual representation of what you wrote. Special characters and all. No special voodoo ways of writing a la "graffiti" on the Palm. Made a mistake? Scribble it out, it goes away. Or you can opt to have your text remain as a set of handwritten strokes, and have it recognised later (very handy for note taking in meetings, as the "usually" above implies - Newton's HWR doesn't always get it right, and might need some nudging in the right direction, which you can't do when scribbling at full speed).

Alternatively, there are on-screen keyboards, or, in extremis, the newton serial keyboard, which is very handy for programming direct on the device.

With HWR, you get around 20-30wpm, about the same as a *fast* typist on a good keyboard. With OSK, 3-10wpm. The newton keyboard is a bit craptacular though, and you can count on about 15-20wpm using it, along with cramp in the fingers.

With Android on a tablet, you don't have much choice. It's on screen keyboards pretty much all the way unless your device supports hardware keyboards. For standard OSK with prediction, I got about the same as on the Newton (the prediction side of things only seemed to be able to predict one word - "android"). I've heard of 10-15wpm with predictive OSK and a fast OSK replacement you're trained to use (Swype, for example) - about as fast as a "slow" typist. With more training you might get a bit faster.

HWR is good technology. It's fast, and discreet (speech recognition has the potential of being fast, but makes you look like a git, and you can't easily use it in meetings or noisy environments). If you want *really* fast, shorthand recognition could get you into massive wpm speeds - at least as fast as speech and maybe faster. The hardware can do it (my cheapo chinese tablet is, at a conservative guess, 6-10 times as fast as the Newton without taking into account the vector unit and GPU). Fast, accurate HWR is no idle dream.

There's other failings with Android's input methods: they hide the entire screen when you're using them, so you have no context - try entering data into a form, and you'll be given a "next" button indicating that entering the current data will take you to the next form field, but there's no indication of what this, or the next, form field actually are. Barking bloody mad, that is. Maybe it's fixed in Froyo.

Inter-app communications

Nothing standard under Android. Some apps share, some don't.

This is more or less the system under Newton as well, but it also has "Assist", and that's available to all apps. Yep, that button that looks like a question mark. What does it do?

From some app, maybe a word processor, scribble "send to Mark", and select it. Hit "assist". Newton goes off and looks, finds that Mark might mean 2 people, and that sending might mean faxing or emailing. Asks who, and how. And then goes off and does it. "Call Fred", Assist, and the telephone dialer fires up, dials the number, and then puts a call logger up, allowing you to scribble notes whilst chatting.

"Assist" is mad cool, and it was available in the early '90s.

The built in apps under Newton *do* share data, and the interface for sharing that data back and forth was available to other developers' apps. the same is more or less the case under Android, although it's hard / impossible for a developer to shoehorn additional stuff into an existing app (as could be done under Newton) without modifying and recompiling.

Synchronisation and so on

The Newton synchronises nicely with desktop apps via serial, ethernet, wifi, bluetooth. As long as you have a sync app, of course. They're pretty hard to come by these days, and it's getting difficult to use a newt with a "modern" desktop OS. You now need need 3rd party software to sync with a Mac, but I'll give the Newton a pass on that as the OS the Apple-supplied software ran on hasn't been current for nearly 10 years. Dunno if the windows sync stuff works on Vista/7, but it certainly ran on XP. 64 bit might be what fraks it totally.

Android mainly syncs, as far as I can tell, with "the cloud", which can largely be considered a euphemism for "Google's ads". Well, frankly, fuck the cloud. Desktop syncing is payware, so fuck that too. It really shouldn't be something one needs 3rd party software for - there *should* be some sort of extendable conduit for syncing - hell, OSX provides most of that anyway.

Other stuff

Let's be honest, Android does have a bunch of stuff it can do waaaaay better than the Newt. Video and audio playback is potentially loads better, mainly down to 12 years of additional hardware development. My cheapo tablet has more hardware potential than a top-of-the-range laptop from the Newton era, after all. That said, video playback under Android leaves a lot to be desired. the hardware should have the power to do NLE on video, and in most cases you can't even play stuff back unless it's in a specific format with a specific size. You can't assume codecs are there. A mess, in short.

The web experience on Android is loads better than on the Newt, too, even if it can't easily do embedded flash video (something I heave a sigh of relief over).

eBooks look nicer under Android. Higher DPI, colour screen. Fine. PDFs don't work at all under Newton, so even having an option to read badly-rendered PDFs slowly under Android is a blessing. That applies to 3rd party readers - I've not used the Adobe reader for 2 reasons:

- On the desktop it's a pile of bloatware crap
- My android device doesn't have Google Market, so I can't get to it.

Photos, idem. Colour screen, higher DPI. Win for Android by default and the inexorable march of progress.

One area the Newton wins on is startup. From "press of button" to the "Happy Newton" chime and a usable device is measured in single digits of seconds. Android takes an age. In addition, the Newton comes back to *exactly* where you were when you turned it off or the batteries ran out, no matter how much time has passed between the two. No data loss, nothing. you're back. No finding files, you're still there. In 15 years of using Newtons, I've *never* lost data (not something I can say of PalmOS devices, for example).

Wakeup - I can't compare. Newton is instant, but my tablet doesn't seem to have any PM stuff enabled, so I don't know if it works or not. I have to hard power cycle it. Sucks, but probably not an Android flaw as such.

As far as gaming goes, Android is more modern. But 99% (or more) of the "games" I've found so far available under Android are made of suck. A lot of this is down to Google's utterly braindead decision to use Java, of all things, as a systems programming language. I mean, really. Gaming suck on a platform that uses a garbage collected langauge with no JIT? Who'd ever have thought it?

And finally, performance.

I have in front of me 2 ARM devices.
One has a 162MHz StrongARM 110 processor, giving 1 DMips/MHz. It has 4MB of RAM and 4MB of flash, with 16MB of additional flash in one of the PCMCIA slots for a total of 20MB *total storage*. It's running a 12 year old, interpreted, prototype based, language.

The other has a 600MHz Cortex-A8 processor, which gives 2 DMips/MHz, and has, in adddition, a vector floating point unit, NEON FP extensions, and an OpenCL-enabled GPU. Even without using the addons, it's nearly *10 times* as fast as the Newton. It has a 13 stage superscalar pipeline and more cache than the Newton has main memory. It has 256MB of Main memory and 2GB of flash, with another 8GB of flash in the SD card slot for a total of 10GB storage. It's running software that's mainly written in Java. Oh, did I mention that the processor itself is optimised for Java?

Guess which one feels "snappy"? Yep, you're right - the hardware specs don't make up for the software implementation.

The "feel" of Android 2.1 makes me believe that the vaunted 450% speedup of Froyo's improved Dalvik are probably not overstated. IUt also makes me wonder why, if there was that much speedup to be had, why it wasn't "had" before initial launch of Android. And how much more there is to be had under the hood. Android's been out for over 2 years now; I'm hardly an early adopter.

No, really. Four hundred and fifty fucking percent faster. What the fuck?

Teardown, and comparison to the Newton.

2010-07-10T16:19:00.000+02:00

So, I tore the wits almost all the way down, and at least far enough to get a look at both sides of the motherboard. I didn't get closeups of the chips, because the little button boards are glued in place and removing them looked like it was gonna be a bit too delicate for a slightly inebriate hardware tech...

Photos are in this set, and here's a taster:

The hardware is impressive, The case has brass inserts for the screws rather than being the usual self-tapping crap, and the motherboard is *not* the mess of patch wires and crappy soldering I was led to expect.

Comparison time. Let's look at the witstech A81 vs a Newton 2x00. Remember, I am biased, so I may be appearing to be harsh, but I will try to at least explain *why*.

Form Factor

Although the Newton is slightly longer for a smaller screen, it wins on ergonomics as opposed to aesthetics. The big "chin" gives something to hold onto in landscape mode, and the slightly "slimmer in the middle" case suggests (and indeed gives) a comfortable "portrait" mode grip. The wits, on the other hand, has nothing much to hold onto, and the case is slippery as oppoed to the Newton's slightly "rubbery" feel. "How do I hold this" was one of my first thoughts when I picked it up.

The Newton also scores highly for its removable flip-over hard lid (screen protection), large stylus and pop-out stylus holder. Even the power supply scores well, with a bunch of adaptors supplied and easily interchangeable on the wall-wart.

Screen

No contest here. The chinaman takes it hands-down, in terms of clarity, resolution, brightness (although the Newton's backlight *is* 12 years old, so...) and so on. It also beats the Newton in terms of touchscreen performance, mainly because this particular example has a bad case of "the jaggies".

Other hardware issues

The wits has a useful stand. I'm tempted to cancel this out with the Newton's ability to run on 4 AA pencells if you need it to. Newton's (single) speaker is pretty good, but the hardware behind it lets it down.

Battery life

No contest. Newton, hands down. *Weeks* on a set of pencells, and you can happily let it simply run out of power, leave it for months, shove in a new set of batteries and you're *exactly* where you were when you put it down. That said, the wits does get an honourable mention for having a removable, and relatively high-capacity, battery. It's far better than most; I got 4 hours 45 minutes running "Operation Sandstorm" continuously ( load average 4, exercising the GPU and CPU pretty hard).

Networking

Both Wits and Newton can do bluetooth and wifi (although it's getting hard to find 5V PCMCIA wifi cards these days, and you're not gonna get anything other than 802.11b). The newt can happily do dialup, fax, or direct serial connection (this one is usually used as a serial terminal on my Sun Netra, actually). Oh, and IRDA. And Localtalk. That said, you can probably do most of that with the wits, given a usb device, some drivers, and a following wind, but would you actually *want* to?

I'll give this one to the wits, as Wifi and bluetooth on the Newt are "kinda neat", but painful to set up. I'm assuming there will eventually be some android support for the wits' bluetooth chipset here...

Expandability

Grudgingly, the wits takes this. The newt has 2 PCMCIA slots, but in real world usage, one of those is gonna be taken up by a flash card. The little serial dongle on the newt is a pain in the ass, too. USB and a microSD slot show that some things *have* oved on in 12 years.

Cool Factor

Are you Joking? Newton by a mile. It's still got a multicoloured Apple on it, for ${DEITY}'s sake.

If I'm honest, the Wits is a nicer machine overall, and undoubtedly massively more powerful, but the Newton shows areas where it could have been vastly better in a purely hardware sense. A shame, because wits have obviously poured some love into this - it's not crap.

I will return to this later, with Newton vs Android in a software sense.

A New Toy

2010-07-07T20:26:00.001+02:00

Well, I finally cracked. I'd been staying away from the Apple store, lest I inadvertantly find myself the owner of an iPad, when I came across Archos' 7 Home Tablet - a nifty looking little 7" screened "mobile internet device", running Android.

So I ordered one.

After a while (quite a while, actually), and 3 calls from Archos telling me my order had been put back again, I got a bit steamed with Archos and told them where they could stuff their 7" rigid object. If you catch my drift.

However, I'd sort of got hooked on the idea of a 7" replacement for my ageing Newton MP2100, so I started casting around and eventually found witstech, who produce the A81, a nifty looking 7" device with GPS, a Cortex-A8 processor, and all for less moolah than the Archos. Score!

So I contacted them, and purchased a brand spanking new, hot off the presses A81(E) (The E meaning that it has extra buttons for Android usage, but more on that later).

So, sure as eggs is eggs, it got a bit delayed. But it did eventually get here.

Review time.

Out of the box, I find: One 7" tablet, half of the back removable, and a replaceable battery that slips nicely behind the back. Okay. One mini USB B to female USB A cable, one generic 5v, 1.5A charger (and they were kind enough to send one that had the right sort of plug for France, score one for Wits tech people), and (as I have a developer model), a little mini-USB B to 1.8V serial adaptor. The latter item looks like a mini-USB plug with 3 hand-labelled wires hanging out of it. Oh, and a nice enough little semi-hard-case.

shanzai.com's unboxing video and overall photos can be found here. Note that hey got a few extra goodies that I didn't like a car charger (already got one) and holder (don't need one).

In terms of finish, the outside of the hardware is not so bad, considering the price. It's lightweight, and has a relatively clean look overall. Although lightweight, it feels tough enough. A bit "chubby" in terms of depth if you're used to looking at Apple gear, but that's tolerable.

Battery is marked 3000mAh, 3.8v. That's a couple of massive plus points - not only is it a load more beefy than the majority of the competitors' offerings, but it's also removable / replaceable. More on battery life later.

The stylus (which is tiny, about the same size as a DS stylus) has a tendency to jam in the holder if you don't push it in "just so" (and it has nothing to help you with alignment - 1 point for industrial design there).

Nothing much to say about the power and USB ports, which seem solid enough. The audio out port looks "odd", or rather "cheap". We'll come to audio later.

The MicroSD card slot hides behind a little rubber grommet, which is normal, although it doesn't look overly waterproof. It's a push/push slot, but seems to be mounted a little too far out, it's hard to get the rubber grommet in place with a card in there. Half a mm further in wouldn't have hurt.

The stand is a nice addition, pulls out from the back and holds the unit at a usable angle.

Button-wise, on the "top" of the unit we have a power button, which (being clear, and retro-lit with LEDs) also doubles as a charging / level indicator as far as I can tell. Green for fully charged, orange for charging, I think. Next to that, there's a pair of left-right buttons, one unit as a "rocker". Looks very nuch like a volume up/down pair, and, oddly enough, that appears to be what it's intended as. On the front, at the bottom left, there are 3 more buttons, with icons corresponding to "home", "back", and "menu". The thin plastic sheet over the fasia around these buttons is already coming away, and from photos it appears that this is endemic - I haven't had the guts to completely remove the sheet and see if it's just "packing protection" though.

Touchscreen is shiny, and has the slightly greasy feel that is common to most resistive devices. The LCD panel itself is bright (20% brightness is more than enough in most circumstances), clear, and (at least on mine) has no dead pixels. The 800x480 resolution gives roughly 135dpi, which makes for a nice enough display. Viewing angle range is "OK", at about 90° horizontally and 60° vertically before it's difficult to see.

On the back we have 2 speakers, oddly positioned vertically (assuming a "widescreen" mode of usage), one over the other. Left and right would have been tricky with the battery placement, I guess, and I'm not expecting hifi quality sound from built in speakers anyway.

On firing the device up, we find, horror of horrors, WinCE. Never has a user experience been so well summed up by its name. Wikipedia tells me that winCE has been out for 13 years, but it doesn't appear to have moved on at all - it still feels like Win 3.0 badly shoehorned into a portable device. It gets everything wrong. *Everything* runs full screen. Microscopic close buttons right next to other microscopic buttons - even with the stylus it's hard to hit the right one (and the touchscreen calibration is pretty much pixel perfect). This is obviously the build for the previous A81 with no buttons, because the buttons themselves don't do anything other than make a "click" noise. Even though I've told WinCE not to click. At all. Bastarding pile of shite.

Wifi performance is fine, it picked up my access point straight away and gave me decent speed. The antennae don't seem overly sensitive (I'd like an external antenna port, myself), but hey - it works. Bluetooth appears functional, although the godawful WinCE interface (particularly the disappearing keyboard) meant that I couldn't actually get the device to pair with my mac more than once.

WinCE, surprisingly enough, managed to use a USB keyboard and mouse through the supplied USB cable. Nice. Couldn't make my Mac see it as a USB storage device through a standard USB cable though. This may be an issue with the Mac, as I had the same problems with Adroid.

Before we do away with WinCE, though, let's look at the quality of the speakers (and the reasons for this will be come obvious later). Playing through the speakers sound quality is at least "OK", at least up to about 80% volume (about the volume of a relatively "loud" radio), at which point things start to distort badly. Cheap speakers, don't expect to use them for much.

So, we hate WinCE. Still alpha quality after 13 years. But we knew that.

Let's reflash with Android and see where we get. After all, Wits have just released an english language Android 2.1.

Reflashing is a piece of piss, once you have the SD card formatted properly (a bit tricky on the Mac, as it craps all over the disk as soon as it's formatted and the booter needs to be the very first item in the FAT, but a bit of VirtualBox voodoo gets us there). Power on, whilst holding down the "left" button, and leave it alone for a few minutes.

Now, some of my gripes about Android are related to the fact the Android I have here is a beta. Some are to do with Android itself, which I'm not really a fan of. Bear this in mind as you read on.

So, we power on, and we get a 4-colour quadrant display as the kernel loads, followed by a bunch of android robots, and finally an animated "android" logo. Boot is pretty quick, but it should be, it's solid-state after all.

Out of the box, we don't have much. For some reason, wits have left "phone" and "camera" functionality in place despite the tablet having neither. A bit daft, that.

No google Apps, (particularly "market").

Bluetooth doesn't want to play, at all. this is, I suspect, a wits issue, or quite likely something to do with kernel drivers for the WL1271 wifi/bluetooth/fm chip. The end result is the same - no bluetooth.

Battery status monitoring is also not included, it seems - the unit reports itself as being on charge, 100% charged, all the time. That sucks, but at least the power button indicates the charging state.

Sleep doesn't appear to function - I suspect that there's no power management going on at all. Surprisingly, this still allows the unit to function for 7-8 hours with wireless turned on and decoding music (but not playing it through the speakers - my wife would have killed me for leaving it turned on all night making noise).

Sound drivers give almost zero volume on the external speakers. That's gonna be a wits bad as well.

For the rest, everything seems to function properly. Calibration is good, again (although the fucking idiot who decided recalibration of the touch panel should require a reboot wants taking out back, shooting, and burying next to the bloke that decided changing network settings in WinNT required a reboot).

I find Android *very* difficult to get along with. Swipes are taken as taps, taps as swipes, and the keyboard / input handling is painful. I've found this to be the case on Android phones, too, but it sometimes makes me want to throw the damned thing at a wall.

The onboard browser is pretty good (no flash, thankfully), renders pretty fast, and appears to work OK. I might try mini opera to get some adblocking, though.

Although the onboard speakers are not properly driven by Android, the external audio is plenty loud enough, and without the usual underlying low-level hiss of cheap audio gear (tested with FLAC rips of Om's "At Giza" and Miles Davis' "Jeru"), and doesn't overload even with some really nasty noise pushed through it (Mainliner's "Black Sky"). As an audio player it's pretty good.

Gaming-wise, Quake3 runs nicely at 30-40fps, and Modern Combat:Sandstorm is equally playable (although multi-touch would be handy for this). Radiant Lite is a nice little "old school" shooter, too.

I haven't tested video playback, but given the gaming performance, it shouldn't be an issue.

Other apps were less endearing, and indicative of what the average android experience might be, regardless of platform. Many apps don't bother to check screen size, and run in a little window on the screen. That's just lazy coding. Others crash with no explanation, or simply hang. Again, bad coding - if they are crashing because of missing features, there should be some sort of feedback.

The device does miss a few features that Google, in their wisdom, have deemed "compulsory" for Android devices, namely: accelerometer, compass (and, to my chagrin, in my case, GPS). Not that I really need another GPS enabled device, but hey, I was kinda looking forward to playing "Zombies! Run!".

Overall, Android still feels part-finished, even allowing for the missing functionality of a beta release. That's part of the overall Google "permanent beta" thing, I guess. It's not awful, and it's certainly better than Wince, but that's not saying much.

More later. Hopefully I'll be able to find my spudgers and do a teardown, and I'll do a side-by side comparison versus my Venerable Newton.

Later

Simon

Performance, performance, performance

2009-12-06T11:59:00.000+01:00

Let's look at improving the performance of the synthesis code I had written. It's pretty nippy, but we can shave some cycles off it, I'm sure. Remember, we're running an interrupt at 32kHz, and then using a divider per "virtual oscillator" to synthesize our waveform; given that we toggle the volume up or down per interrupt, that gives us a maximum frequency of 16kHz. On top of that, the high frequency range response is going to be pretty poor, as illustrated below

"Ticks"  Frequency  Note (approx)
0x0000 = 16kHz
0x0001 = 8kHz
0x0002 = 4kHz     = C8
0x0003 = 2.6kHz   = E7
0x0004 = 2 kHz    = C7
0x0005 = 1.6kHz   = G6
0x0006 = 1.3kHz   = E6
0x0007 = 1.143kHz = D6
0x0008 = 1kHz     = C6
0x0009 = 0.89kHz  = A5

As can be seen, we don't even begin to hit (for varying values of "hit", those with perfect pitch need not apply) every note until we get down pretty low. If we up our interrupt rate to 64kHz, we get the following:

"Ticks"  Frequency  Note (approx)
0x0000 = 32kHz
0x0001 = 16kHz
0x0002 = 8kHz
0x0003 = 5.3kHz 
0x0004 = 4 kHz    = C8
0x0005 = 3.2kHz   = G7
0x0006 = 2.6kHz   = E7
0x0007 = 2.3kHz   = D7
0x0008 = 2kHz     = C7
0x0009 = 1.78kHz  = A6
0x000a = 1.6kHz   = G6

That gives us a much better spread, and still leaves us plenty of sub-audio / LFO range at the bottom. However, 64kHz only leaves us 256 cycles to play with, and our existing code only leaves us about 50 cycles of headroom for other code, like dealing with user interface and actually twiddling frequencies. Not good enough. Also, it would be nice to have per-channel fading.

So, first off, let's look at the original code.

f_timer_interrupt:
        clr     _volume         ; 1     ; volume to zero
        ld      a, #0x07        ; 1     ; set initial channel flag
        ldw     x, #_channels   ; 2     ; load y register with address of channel data
dochannel:
        ldw     y, x            ; 1     ; Load y register with ticks_left
        ldw     y, (y)          ; 2
        jrmi    br3             ; 1 / 2 ; skip if channel is off (bit 15 of ticks_left set)
        decw    y               ; 2     ; decrement
        jrpl    br1             ; 1 / 2 ; if not negative, skip
        ldw     y, x            ; 1     ; reset ticks_left
        ldw     y, (0x02, y)    ; 2
        ldw     (x), y          ; 2     ; store ticks left
        jra     br2             ; 2     ; and skip unnecessary work
br1:    ldw     (x), y          ; 2     ; store ticks_left
        ldw     y, x            ; 1     ; get number of ticks per cycle
        ldw     y, (0x02, y)    ; 2
br2:    srlw    y               ; 2     ; divide by 2
        cpw     y, (x)          ; 2     ; compare with ticks_left
        jrmi    br3             ; 1 / 2
        inc     _volume         ; 1     ; increment volume
br3:    addw    x, #0x0004      ; 2     ; go 4 bytes up the channel data list
        dec     a               ; 1
        jrpl    dochannel       ; 1 / 2 ; go around if we have more channels to do
               
        bres    0x5255, #0x00   ; 1     ; Clear TIM1 Interrupt pending bit
        iret                    ; 11    ; and return

Okay, it's pretty good, but an obvious optimisation would be to "unroll the loop", which saves us a few cycles per channel. Unfortunately, this is gonna make our code unreadable and unmaintainable, a great long string of assembler.

That's what macros are made for. Macros are a bit like the C preprocessor on steroids, you can define a bunch of "inlined" code as a macro, that will be substituted into the code.

So, what we're going to do is write a macro that deals with any particular channel. Having 8 instances of a macro avoids the loop, without rewriting the same code over and over again. Nice. On top of that, we can pass in the "channel base address" to the macro, and avoid all the "ld y, x; ld y,(y)" tango we were required to do. That's good for a load of cycles per iteration, and gives us enough headroom to do channel fading as well.

So, let's redefine our structures, adding a per-channel volume control. We'll use this, instead of the hokey "top bit" approach taken previously, to know if we can exit fast.

typedef struct {
        u8      volume;
        u16     ticks_left;
        u16     ticks;
} channel;

Now, in our assembler code, we change the way the zero-page variables are laid out, to match.

switch .ubsct
_channels:
chan0:  ds.b    5
chan1:  ds.b    5
chan2:  ds.b    5
chan3:  ds.b    5
chan4:  ds.b    5
chan5:  ds.b    5
chan6:  ds.b    5
chan7:  ds.b    5
_volume: ds.b    1
; make them visible to C code
xdef _channels
xdef _volume

We keep the "top" label for C, and then we have individual channel labels for the assembler code (we could use simple math, but this makes things more explicit).

Now, the macro itself.

dochan: macro \chan
        ld      a, \chan        ; 1     ; move volume to accumulator
        jreq    \@done          ; 1 / 2 ; quit if zero volume
        ldw     x, \chan + 1    ; 2     ; get ticks_left
 ldw     y,     \chan + 3       ; 2     ; load ticks
        decw    x               ; 2     ; decrement ticks_left
        jrpl    \@br1           ; 1 / 2 ; branch if still ticking
        ldw     x, y            ; 1     ; load ticks
\@br1:  ldw     \chan + 1, x    ; 2     ; store new ticks_left
        srlw    y               ; 2     ; divide ticks by 2
        cpw     y, \chan + 1    ; 2     ; compare with ticks_left
        jrmi    \@done          ; 1 / 2 ;
        add     a, _volume      ; 1     ; add volume
        ld      _volume, a      ; 1     ; and store
\@done:
endm

Passing in a base address, this will handle the calculations for a single channel. Best case performance (channel muted) is a mere 3 cycles, best case (channel non muted) is 18 cycles, worst case is 19 cycles. Any given channel will spend half of its time at 18 cycles and half at 19 cycles, giving us an average of 18.5 cycles / non-muted channel. There's probably a few more cycles to shave off there, too.

Calling the macro is simple.

f_timer_interrupt:
 clr     _volume                ; 1     ; volume to zero
 dochan  chan0                  ; 18.5
        dochan  chan1           ; 18.5
        dochan  chan2           ; 18.5
        dochan  chan3           ; 18.5
        dochan  chan4           ; 18.5
        dochan  chan5           ; 18.5
        dochan  chan6           ; 18.5
        dochan  chan7           ; 18.5
        bres 0x5255, #0x00      ; 1     ; Clear TIM1 Interrupt pending bit
        iret                    ; 11    ; and return

As can be seen, the static overhead is now down to 13 cycles, so assuming all channels are "on", worst case time taken is going to be 13 + (19 * channels). For 8 channels, this is 165 cycles (161 cycles average). That fits quite neatly into the 256 cycles we have per interrupt, with 90-odd cycles left over. Not only that, but we can easily trim down the number of channels to fit if needs be - if we wanted, for example, 4 channels would take only 89 cycles, or 6 channels (for 4 drones and 2 LFOs) 127 cycles, or 50% CPU.

That's pretty good. But we can do better.

Let's think about how we are going to go about getting audio off the board. An R-2R network would work, but uses up to 8 pins and a bunch of additional hardware - why do extra work when we can let the processor do the hard lifting for us? What we need is to use hardware PWM, and all we need then is a single pin and a lowpass filter. As this is all going to be thrown out to a set of analog filters anyway, a single-pin approach seems more than reasonable. Now, we're already doing PWM for the LED brightness, so why not generalise that?

So. First of all, we set Timer 3 to a prescaler of one and period of 256. That gives us 8-bit PWM, straight off the bat. We can now do away with the 'volume' variable, and rather than storing stuff in and out of memory, do it all in the accumulator, dumping that direct to the timer at the end of the interrupt. We lose the extreme time saving of skipping when a channel is set to volume zero, but we gain speed and cycles overall.

Here's the new assembler code:


dochan: macro \chan
        ldw     x, \chan + 1    ; 2     ; get ticks_left
        ldw     y, \chan + 3    ; 2     ; load ticks
        decw    x               ; 2     ; decrement ticks_left
        jrpl    \@br1           ; 1 / 2 ; branch if still ticking
        ldw     x, y            ; 1     ; load ticks
\@br1:  ldw     \chan + 1, x    ; 2     ; store new ticks_left
        srlw    y               ; 2     ; divide ticks by 2
        cpw     y, \chan + 1    ; 2     ; compare with ticks_left
        jrmi    \@done          ; 1 / 2 ;
        add     a, \chan        ; 1     ; add volume
\@done:
endm

; 14 + (16 * 8) = 142 cycles
f_timer_interrupt:
        clr     a               ; 1     ; initial volume to 0
        dochan  chan0           ;
        dochan  chan1           ;
        dochan  chan2           ;
        dochan  chan3           ;
        dochan  chan4           ;
        dochan  chan5           ;
        dochan  chan6           ;
        dochan  chan7           ;
        ld 0x5330, a            ; 1     ; Store volume in TIM3 PWM register
        bres 0x5255, #0x00      ; 1     ; Clear TIM1 Interrupt pending bit
        iret                    ; 11    ; and return

That gets us down to 16 cycles per channel in *all* cases, leaving us with a total of 142 cycles for the entire interrupt (just over 50% of CPU), with 8 channels.

Our main loop is, of course, now reduced to a simple

while(1);

Moving from flashy LED action to annoying drony noise action is a simple case of switching to TIM3_OC1, which outputs its PWM on Port D pin 2 - hooking a speaker across CN4 pin 7 (PD2) and CN1 Pin 4 (GND) indeed gives us an annoying drony beaty noise after pushing some of the virtual oscillator frequencies into the audio range.

Software Synthesis. Gotta love it.

Why Assembler is better

2009-12-06T09:08:00.000+01:00

Following on from my last post, I thought I'd expand a little on how assembler is better than C. On "real" computers, it's often said that a C or C++ compiler will, in the vast majority of cases, produce better code than you can do by hand in assembler. This is largely true, especially when you're dealing with multiple cores and the like.

On microcontrollers, however, and especially 8 / 16 bit ones, the C compilers aren't "all that", and the additional overhead imposed by a C compiler can kill your application stone dead.

Let's take a concrete example.

In my (very non-optimal) assembler example posted before, I need to clear the interrupt pending flag for the Timer interrupt I'm servicing. This is easily done in assembler, it's a one-line, one clock cycle instruction, as follows:

bres        0x5255, #0x00   ; Clear TIM1 Interrupt pending bit

Simple, right? Now, let's look at what the C compiler gives us.

Here's the "C" code we use:

// Clear the interrupt pending bit for TIM1.
TIM1_ClearITPendingBit(TIM1_IT_UPDATE);

Simple enough, right? There's obviously the overhead of a function call, but we might expect the guts of the function to do a simple bit of inline assembler as above. Let's look.

void TIM1_ClearITPendingBit(TIM1_IT_TypeDef TIM1_IT)
{
    /* Check the parameters */
    assert_param(IS_TIM1_IT_OK(TIM1_IT));

    /* Clear the IT pending Bit */
    TIM1->SR1 = (u8)(~(u8)TIM1_IT);
}

So, let's look at what that C code produces.


main.c:64  TIM1_ClearITPendingBit(TIM1_IT_UPDATE); 
0x91c3            0xA601          LD    A,#0x01             LD    A,#0x01 
0x91c5            0xCD8C9C        CALL  0x8c9c              CALL  _TIM1_ClearITPendingBit 

...

stm8s_tim1.c:2156     TIM1->SR1 = (u8)(~(u8)TIM1_IT); 
0x8c9c <.ClearITPendingBit> 0x43            CPL   A                   CPL   A 
0x8c9d <.earITPendingBit+1> 0xC75255        LD    0x5255,A            LD    0x5255,A 
stm8s_tim1.c:2157 } 
0x8ca0 <.earITPendingBit+4> 0x81            RET                       RET

So, we load the accumulator with a value, that's one cycle. Call a function, 4 cycles. Complement the accumulator, one cycle. Store the accumulator in the flag, 1 cycle. Return from function, 4 cycles.

In total, that's 11 cycles and 10 bytes to do the same thing we did in one cycle and 3 bytes. "inlining" this function doesn't make our code any fatter, either, as the 3 bytes we're using are the same as the 3 bytes we would have used to call the function.

What we do lose is readability, but that's easily enough got back by writing macros.

Mixing Assembler and C on the STM8S-Discovery board

2009-12-05T21:23:00.000+01:00

So, been playing with my STM8S-discovery boards, here's some stuff you might like. This builds on Ben's stuff here - http://www.benryves.com/journal/3567231

Now, one of my projects is to do with making a multi-channel drone synthesizer. I should really do it with discrete logic and amps, but hey, it's a quickie. What I want to do is 8 channels of audio-range square waves, at differing and varying frequencies. How we go about varying the frequencies is another matter, but the main problem is doing 8 channels - I could do 4 with just the timers, but 8 is pretty tricksy.

Basically, the approach I'm taking is to use a timer firing at a regular frequency, and do additive synthesis to make the final output volume (I'll initially be using a simple approach with no fading of the 8 pseudo-oscillators, so the maximum output volume is 8; that lets us get away with a 4 pin R-2R DAC (but more on that later).

Now, we need to work out how much we can do, and how long we have to do it. The clock of the disco board runs at up to 16 MHz, so we can work out easily enough what frequencies we can call our hypothtical interrupt at. The prescaler value gives us, direcly, the number of clocks we have to play with at that frequency

1024 = 16kHz
512 = 32kHz
256 = 64kHz
128 = 128kHz

and so on. Bearing in mind that human audio range peaks at ~20kHz, we'd probably like to be using a 32kHz or better clock. Indeed, due to the way my software works, I can only generate up to 16kHz with a 32kHz clock, and there's a really coarse granularity on the high end - it's basically not much cop above 1kHz or so, around 2 octaves up from middle C.

Anyway, 512 cycles is not much to play with. We're gonna need some assembler. C code is waaaay too fat. My first cut interrupt routine has a "worst case" of just over 200 cycles, so that cuts out 64kHz if we want to do anything clever elsewhere. And we do. So, 32kHz it is, and my interrupt is gonna use around 1/3 of total CPU all by itself. I should be able to streamline it a bit (or even a lot), but I doubt it's ever going to be able to run at 64kHz. As an idea of how fat C code is, the equivalent C routine had a worst case of 500 cycles. Yowza.

So, how do we make our assembler code work with existing "C"? Well, first thing to do is take a trivial program and compile it; in the "Debug" folder of the project you'll find the generated assembler code (for example, main.ls) - look at this and you can find out how the name mangling works.

In my case, I was interested in the names of functions and global variables, so I compiled up a quick program with one global variable and one function.

For a function name of "MyFunction", the actual label generated in the assembler (and thus the format of the name we need to use) is "f_MyFunction". Groovy. Variables have an underscore, so "my_var" becomes "_my_var". Now we know that, we can do some work.

First, we edit the interrupt table, adding an "extern" reference to our assembler routine. This stops the C compiler kicking up a fuss.

extern @far @interrupt void timer_interrupt(void);

Now, we add a reference to that routine to the table itself.

...
{0x82, timer_interrupt}, /* irq11 */
...

I'm using irq11 because that's the timer 1 overflow interrupt.

Now. I'm going to need access to the interrupt's data from elsewhere, so we need to add some references to them, too. I've shoved them in main.c.

// For our purposes
typedef struct {
    u16 ticks_left;
    u16 ticks;
} channel;

// Extern, these are defined in synth.asm
extern channel channels[8];
extern u8 volume;

So, we have an array of 8 "channel data" structures, with "ticks" defining the number of interrupt "ticks" before we roll over, and "ticks_left" being the number of interrupt ticks this channel has had since last rollover. Pretty simple, really. There's also a single 8-bit "volume" field. Note the "extern" on both of these - this tells the compiler they are actually defined elsewhere.

As I haven't bothered to wire up an R2R ladder on my board yet, I decided to test with a bit of PWM on the LED. this follows on directly from Ben's stuff.


main()
{
  // Set the internal high-speed oscillator to 1 to run at 16/1=16MHz.
  CLK_HSIPrescalerConfig(CLK_PRESCALER_HSIDIV1);

  // Reset ("de-initialise") TIM1.
  TIM1_DeInit();
  // Set TIM1 to use a prescaler of 512 and to have a period of 1.
  TIM1_TimeBaseInit(512, TIM1_COUNTERMODE_UP, 1, 0);
  // Set TIM1 to generate interrupts every time the counter overflows.  With
  // prescaling of 512, this is a frequency of 32kHz
  TIM1_ITConfig(TIM1_IT_UPDATE, ENABLE);
  // Enable TIM1.
  TIM1_Cmd(ENABLE);

  // For visualisation only
  // Reset ("de-initialise") TIM3.
  TIM3_DeInit();
  // Set TIM3 to use a prescaler of 1 and have a period of 999.
  TIM3_TimeBaseInit(TIM3_PRESCALER_1, 999);
  // Initialise output channel 2 of TIM3.
  TIM3_OC2Init(TIM3_OCMODE_PWM1, TIM3_OUTPUTSTATE_ENABLE, 0, TIM3_OCPOLARITY_LOW);

  // Enable TIM3.
  TIM3_Cmd(ENABLE);

  // Set up our channels
  channels[0].ticks_left = 0;
  channels[1].ticks_left = 0;
  channels[2].ticks_left = 0;
  channels[3].ticks_left = 0;
  channels[4].ticks_left = 0;
  channels[5].ticks_left = 0;
  channels[6].ticks_left = 0;
  channels[7].ticks_left = 0;
  channels[0].ticks = 0x4000;
  channels[1].ticks = 0x4010;
  channels[2].ticks = 0x4020;
  channels[3].ticks = 0x4040;
  channels[4].ticks = 0x4080;
  channels[5].ticks = 0x4100;
  channels[6].ticks = 0x4200;
  channels[7].ticks = 0x4400;

  enableInterrupts();

  while (1) {
    TIM3_SetCompare2(volume * (1000 / 8));
  }
}

What's interesting is the setting of the various channels to different (very low frequency) rollover periods - it starts off with everything together, and the channels slowly end up "beating" against one another, which does "interesting" stuff to the LED. The LED itself is PWM controlled to set its brightness to one of 8 levels.

Of course, none of this is any good without the interrupt routine itself. This goes in a totally separate file with a ".asm" extension. The toolkit knows how to deal with it.


; names mangled to C code specs
; uninitialised data in page zero
switch .ubsct
_channels:
                ds.w        16
_volume:
        ds.b    1

; make them visible to C code
xdef _channels
xdef _volume

; code
switch .text
f_timer_interrupt:
        clr     _volume         ; 1     ; volume to zero
        ld      a, #0x07        ; 1     ; set initial channel flag
        ldw     x, #_channels   ; 2     ; load y register with address of channel data
dochannel:
        ldw     y, x            ; 1     ; Load y register with ticks_left
        ldw     y, (y)          ; 2
        jrmi    br3             ; 1 / 2 ; skip if channel is off (bit 15 of ticks_left set)
        decw    y               ; 2     ; decrement
        jrpl    br1             ; 1 / 2 ; if not negative, skip
        ldw     y, x            ; 1     ; reset ticks_left
        ldw     y, (0x02, y)    ; 2
        ldw     (x), y          ; 2     ; store ticks left
        jra     br2             ; 2     ; and skip unnecessary work
br1:    ldw     (x), y          ; 2     ; store ticks_left
        ldw     y, x            ; 1     ; get number of ticks per cycle
        ldw     y, (0x02, y)    ; 2
br2:    srlw    y               ; 2     ; divide by 2
        cpw     y, (x)          ; 2     ; compare with ticks_left
        jrmi    br3             ; 1 / 2
        inc     _volume         ; 1     ; increment volume
br3:    addw    x, #0x0004      ; 2     ; go 4 bytes up the channel data list
        dec     a               ; 1
        jrpl    dochannel       ; 1 / 2 ; go around if we have more channels to do
               
        bres    0x5255, #0x00   ; 1     ; Clear TIM1 Interrupt pending bit
        iret                    ; 11    ; and return
               
; make function visible to C code
xdef f_timer_interrupt

You'll note the name mangling, and the "xdef" lines to make the labels externally visible. Also, that I've somewhat anally added the number of cycles per operation to the source.

This routine allows me to kill any one channel at the next call to the interrupt by setting its "ticks" value to 0x8000, and "ticks_left" to 0x0000.

Hope this is of some use to people.