KQK4663

Archive for the 'Uncategorized' Category

Integer promotion in C

jake April 22nd, 2008

unsigned char t0, t1;
unsigned int diff;
t0 = 0;
t1 = 255;
diff = (unsigned int)(t0 - t1);
printf("difference: %x\n", diff);

Intuitively, I would think that the result of the subtraction would be an unsigned char with value 0x01, which then would get converted to an unsigned int with value 0x00000001 (assuming a 32-bit platform).

Instead, when the program is compiled and run, the output is:

difference: 0xffffff01

Turns out that my compiler is actually doing the right thing here, but C is playing tricks on me.

The C standard has a concept of integer rank. long long has greater rank than long which has greater rank than int, which has greater rank than short, which has greater rank than char. Unsigned types have the same rank as their signed counterparts. Note that even if two integral types have the same size in bits, their rank is different.

For arithmetic operations, the standard specifies that operands of integral data type are promoted to integer rank when their rank is less. Historically, there were two ways of doing so, called unsigned preserving and value preserving. The former simply converts all unsigned chars and shorts into unsigned ints. The latter converts them to signed ints if they are smaller and unsigned ints otherwise (i.e. if short and int are the same size, unsigned shorts will be converted to unsigned ints).

In 1974, Kernighan and Richie's The C Programming Language set the original C standard, and specified the unsigned preserving method. But in 1989 the first ANSI C standard switched (after much debate) to the value preserving method, because it reduces the number of situations in which the result of an expression is questionably signed, meaning it could intuitively be interpreted either way. More detail on this distinction can be found in Section 3.2.1.1 of Rational for the ANSI C Programming Language.

So, in the example above, t0 and t1 are promoted to signed ints before being subtracted. On my machine, ints are 32 bits, so the resulting difference is a signed int of value 0xffffff01 (-255).

This is then converted to unsigned int; the C standard specifies this conversion in an interesting way: "...the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type." In a twos-complement system, this is equivalent to leaving the bits unchanged. In our case, this means that the new value is -255 + 4294967296 = 4294967041 = 0xffffff01.

The correct way to cause the desired wrap of in our example is to insert an explicit cast of the subtracted result back to unsigned char:

diff = (unsigned int)(unsigned char)(t0 - t1);

This produces the intended result:

difference: 0x00000001

x86 Addressing and the Segment Descriptor Tables

jake May 11th, 2007

It's easy to think of a C pointer as containing a physical memory location; if my program calls int x = 42; int *p = &x; printf("p = 0x%p\n", p); and the output is p = 0xdeadbeef, I could imagine that dereferencing p would actually set the address bus to 11011110101011011011111011101111 = 0xdeadbeef to read its value. The real story of the x86 is a bit more complicated...

The Intel 8086 has a 20-bit address bus, capable of addressing one megabyte (2^20 bytes) of memory, but only a 16-bit data bus -- all registers are 16 bits wide. To access the entire address space, then, an offset stored in one of the general purpose registers is added to the base address of a memory segment. The segment number is stored in one of the segment registers (CS, where program code resides; SS, for the stack, DS, for global data, and ES, often used for extra program data like strings), and the final address is computed as segment*16 + offset.

The 80286 introduces a 16-bit protected mode, in which the segment registers no longer index physical locations in memory, but rather contain a 13-bit index into a table of 8-byte segment descriptors. 24 bits of these 8 bytes contain a base address, and physical addresses are computed by adding the offset directly to it, allowing 2^24 bytes = 16MiB to be addressed. The descriptors also contain segment limits, allowing the kernel to detect when a piece of code addresses memory it's not supposed to.

There are three table types: the global descriptor table, the interrupt descriptor table, and local descriptor tables. There is a single global table which is available to all processes, but each process can have its own local table. The tables can be located anywhere in memory, and there are special instructions (lgdt, lidt, and lldt) for setting them up. These instructions tell the CPU about both the location and size of the tables; since the table index from the segment register is 13 bits, the maximum table length is 8192 entries.

In addition to the 13-bit table index, the segment register also contains a bit which selects between the global table or the current local table (the remaining two bits specify a privilege level, which I won't discuss here). The x86 architecture distinguishes between the logical address stored in the segment and offset registers visible to the programmer and the linear address, which the CPU forms using the segmentation table lookup. Since we have 13 + 1 bits in the segment register used for addressing and 16 bits in the offset register, logical addresses in the 286 are 30 bits long. The documentation for the 286 will refer to 1 GiB of virtual address space, which refers to logical addressing. Of course, the address bus on the 286 is only 24 bits, and the mapping of logical addresses to linear addresses is not bijective, since the segments described in a descriptor table can overlap. In practice, the CPU raises an exception when a segment register contains a table index which is out of bounds, and the kernel can trap this exception to retrieve the data from its virtual memory implementation.

When protected mode was introduced with the 80286, the old 8086-style of addressing was referred to as real mode. To remain compatible with older code, the 80286 defaults to real mode and must be explicitly told to go into protected mode, from which it could not return without resetting the chip.

The intel 80386 was introduced in 1985 and extended the data bus to 32 bits. The segment registers were still 16 bits, but the segment descriptors they indexed were extended to allow 32-bit base addresses and handle 32-bit offset limits. This scheme is known as 32-bit protected mode.

Since the 386 allows each segment to address 2^32 = 4 Gib of linear address space, it is possible to set up one segment each for code and data, and not worry about segmentation; in fact, this is how the Linux kernel operates. The nice protection features allowed by segment limits can be implemented using the hardware's paging mechanisms, which are not so x86-specific. I'll write about paging in a future article.

How Computers Work, Part 1 - The Keyboard Interrupt Path

jake May 9th, 2007

I was talking with a friend the other day about questions we've used in interviews for programmers. One of my pet peeves is the obscenely specific questions which boil down to "how would you solve this particular problem we have right now?" If I were asked that kind of question in an interview, I would have to wonder if the company was at all interested in the long-term effectiveness of their employees, and whether they care to let them learn and grow into more productive programmers. Interviews need to establish a basic level of competence, but most importantly they need to determine whether the candidate knows what he doesn't know and can learn on the job.

On the other hand, I always tried to avoid asking questions that had nothing to do with programming, such as why are manhole covers round?. My friend told me of a great one he uses: "if I type 'ping www.kqk4663.com' into a terminal at a UNIX box and hit return, what happens?" It's been a while since I thought about the low-level hardware and software that makes ping possible, so as an exercise I wrote up the chain of events that occur on an 80x86 box running Linux:

A typical PS/2 keyboard has an onboard chip which detects keypresses and handles things like "debouncing" the switches. Different keyboards have different key mechanisms, so there is a variety of encoder chips (the Intel 8048 was popular early on), but the end result is a serial data signal sent through the keyboard cord to a controller chip on the motherboard. This data consists of (possibly multibyte) sequences called "scan codes." For each key there are two unique scan codes: a "make code" which is sent when the key is pressed, and a "break code" which is sent when it is released.

The controller chip is an Intel 8042-compatible device which handles decoding the serial stream from the keyboard, and telling the CPU about keypresses. It may also be integrated into the motherboard's chipset. The CPU talks to it via I/O space addressing at locations 0x60 (data buffer) and 0x64 (status/commands).

A typical PC contains two 8259 Programmable Interrupt Controller chips (which may be part of a chipset), or one of it's more advanced descendants.

The first one which controls the INT line of the CPU. It has eight interrupt inputs, IRQ0 - IRQ7, each of which can be hooked up to a peripheral device, one of which is the second "cascaded" 8259 on IRQ2. This allows for fifteen devices to interrupt the PC. The keyboard controller's interrupt line is connected to IRQ1.

When the INT line is raised, the processor immediately pushes the flags register and a return address onto the stack. It then fetches the interrupt vector (which IRQ line generated the interrupt) by lowering the INTA line to retrieve it from the 8259.

Given the IRQ vector, it CPU must look up the address of the code which will handle the interrupt (a.k.a. the interrupt service routine, or ISR). On the original 8086, the CPU expects to find a table of 32-bit ISR pointers at address 0x0. But the 80286 and later processors have a register called idtr, which points to the system's interrupt descriptor table in memory. Either way, the CPU uses the IRQ number as an index into these tables, retrieves a pointer to the ISR, pushes the flags register onto the stack, and jumps to that address. The ISR will return using the IRET instruction rather than RET to tell the processor to pop the flags register.

Now, assuming that it set up the interrupt vector table properly at bootup, the kernel software is handling the interrupt. Next post, I'm going to dig into the Linux kernel and find out how it deals.

Debugging Apple’s LoginItemsAE.c on Intel Macs

jake March 28th, 2007

Came across some wackiness involving the Apple Event Manager and LoginItemsAE.c (Apple's example code for manipulating a user's list of login items). In hopes that others dealing with similar problems will find this:

The "System Events" process can be accessed via an Apple Event (i.e. Applescript) dictionary which allow you to list, add, and delete login items. Login items are described by two parameters, a path to the application to be launched when the user logs in, and a flag which specifies whether it should be hidden once launched.

In LoginItemsAE.c, retrieved login item paths are encoded as typeUnicodeText (native-endian UTF-16) and are converted to CFURLs for the user's consumption, in three steps:

Get a UTF8-converted string in a char buffer using AEGetKeyPtr (#defined to AEGetParam) to "coerce" the parameter to typeUTF8Text.
Make an FSPathRef from the character buffer using FSPathMakeRef.
Use CFURLCreateFromFileSystemRepresentation to get a CFURLRef

On my Powerbook (PPC), this worked fine, but when I sent my beta to testers, MacBook users reported that my "Start At Login" option wasn't working. In debugging, I found that AEGetKeyPtr was returning errAECoercionFail (-1700) -- it couldn't convert the Unicode path to UTF8.

A symmetric problem occurs when asking System Events to add a login item. Here, LoginItemsAE.c uses AECoercePtr to create it's path property in typeUnicode form from a UTF8 character buffer, but was seeing errAECoercionFail on Intel Macs.

Well, that sucks. In Apple's Apple Events Programming Guide, it says

Support for the following coercions was added in Mac OS X version 10.4:

Between these types:

typeStyledText, typeUnicodeText, typeUTF8Text, and typeUTF16ExternalRepresentation

...

In searching for a solution on the web, I noticed that the Growl project also uses LoginItemsAE.c to set their helper app as a login item. The latest repository version shows no changes. Have they not seen the same problem?

The workaround: instead of asking AE to coerce our data for us, we do it ourselves using CFStrings. I wrote a function which converts a char buffer between CF string representations:

static int ConvertPathEncoding(char *path, int pathlen, int bufsize, int src_cftype, int dest_cftype)
{
  int ret = 0;
  CFStringRef cfpath = CFStringCreateWithBytes(NULL, (UInt8 *)path, pathlen, src_cftype, FALSE);
  if (cfpath == NULL) {
    ret = -1;
  }
  else {
    int len = CFStringGetLength(cfpath);
    Size actualLen;
    CFStringGetBytes(cfpath, CFRangeMake(0, len), dest_cftype, 0, false,
                    (UInt8 *)path, bufsize, &actualLen);
    CFRelease(cfpath);
    ret = (int)actualLen;
  }
  return ret;
}

Now I can ask AEGetKeyPtr to give me a typeUnicode string in my buffer, and then call ConvertPathEncoding to convert from kCFStringEncodingUnicode and kCFStringEncodingUTF8. Similarly, instead of calling AECoercePtr to create my login item path parameter description, I call ConvertPathPathEncoding to convert from kCFStringEncodingUTF8 and kCFStringEncodingUnicode.

In AEDataModel.h, we see that typeUnicodeText and some other types are "deprecated due to their lack of explicit encoding or byte order definition. Please use typeUTF16ExternalRepresentation or typeUTF8Text instead." typeUTF16ExternalRepresentation is defined as "big-endian 16 bit unicode with optional byte-order-mark, or little-endian 16 bit unicode with required byte-order-mark,", i.e. it is possible to check if the string has the correct byte-order for the system. But apparently, the System Events API is still using UTf-16 with no BOM.

I needed an outlet