C isupper() function

Question

I'm currently reading "The C Programming Language 2nd edition" and I'm not clear about this exercise:

Functions like isupper can be implemented to save space or to save time. Explore both possibilities.

• How can I implement this function?
• How should I write two versions, one to save time and one to save space (some pseudo code would be nice)?

I would appreciate some advice about this.

Answer 1

One method can do some comparisons with 'A', 'Z'.

The other method can use a pre-computed lookup table.

It's the first suggestion mentioned on the Wikipedia page for time-space tradeoffs.

Answer 2

The classic trade-off is speed versus memory: either compute a result, or look it up in a table.

It should not be hard to figure out how these would look, for the isupper() function.

A few things make it perhaps unexpectedly complicated on today's mainstream CPU:s, though:

A table to support ASCII needs 128 bits, or 256 bits if you don't want to mask off the topmost bit yourself, assuming an 8-bit char. This is only 32 bytes, but that is probably still more than code that exploits the sequential nature of the ASCII mapping. Large code size is generally bad for performance, since it affects cache efficiency and generally exposes the large difference in bandwidth between today's CPU:s and their memory subsystems.

Code using explicit comparisons to compute the result, without exploiting the sequential mapping, will be pretty large, larger than the corresponding look-up table. This is not typical; it's easier to see the difference in the speed-versus-memory trade-off for cases where the code to compute a value is more compact than the look-up table.

Answer 3

You can save both space and time, actually. Upper case characters are contiguous in the ASCII table, so you just have to do this (this doesn't handle locales obviously, but I doubt that is the point of your exercise):

BOOL isUpper(char c)
{
    return (c >= 'A' && c <= 'Z');
}

Answer 4

Upper case characters are ASCII hex 0x41 through 0x5A. That means bit 0x40 is always set. If you are sure that the argument is an ASCII character, you can just return:

(c & 0x40);

Answer 5

One version uses an array initialized with appropriate values, one byte per character in the code set (plus 1 to allow for EOF, which may also be passed to the classification functions):

static const char bits[257] = { ...initialization... };

int isupper(int ch)
{
    assert(ch == EOF || (ch >= 0 && ch <= 255));
    return((bits+1)[ch] & UPPER_MASK);
}

Note that the 'bits' can be used by all the various functions like isupper(), islower(), isalpha(), etc with appropriate values for the mask. And if you make the 'bits' array changeable at runtime, you can adapt to different (single-byte) code sets.

This takes space - the array.

The other version makes assumptions about the contiguousness of upper-case characters, and also about the limited set of valid upper-case characters (fine for ASCII, not so good for ISO 8859-1 or its relatives):

int isupper(int ch)
{
    return (ch >= 'A' && ch <= 'Z');  // ASCII only - not a good implementation!
}

This can (almost) be implemented in a macro; it is hard to avoid evaluating the character twice, which is not actually permitted in the standard. Using non-standard (GNU) extensions, it can be implemented as a macro that evaluates the character argument just once. To extend this to ISO 8859-1 would require a second condition, along the lines of:

int isupper(int ch)
{
    return ((ch >= 'A' && ch <= 'Z')) || (ch >= 0xC0 && ch <= 0xDD));
}

Repeat that as a macro very often and the 'space saving' rapidly becomes a cost as the bit masking has a fixed size.

Given the requirements of modern code sets, the mapping version is almost invariably used in practice; it can adapt at run-time to the current code set, etc, which the range-based versions cannot.