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

Original answer

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 contiguity 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.

---

Extended answer

I still can't figure out how UPPER_MASK works. Can you explain it more specifically?

Ignoring issues of namespaces for symbols in headers, you have a series of twelve classification macros:

• isalpha()
• isupper()
• islower()
• isalnum()
• isgraph()
• isprint()
• iscntrl()
• isdigit()
• isblank()
• isspace()
• ispunct()
• isxdigit()

The distinction between isspace() and isblank() is:

• isspace() — space (' '), form feed ('\f'), new-line ('\n'), carriage return ('\r'), horizontal tab ('\t'), and vertical tab ('\v').
• isblank() — space (' '), and horizontal tab ('\t').

There are definitions for these sets of characters in the C standard, and guidelines for the C locale.

For example (in the C locale), either islower() or isupper() is true if isalpha() is true, but that need not be the true in other locales.

I think the necessary bits are:

• DIGIT_MASK
• XDIGT_MASK
• ALPHA_MASK
• LOWER_MASK
• UPPER_MASK
• PUNCT_MASK
• SPACE_MASK
• PRINT_MASK
• CNTRL_MASK
• BLANK_MASK

From these ten masks, you can create the other two:

• ALNUM_MASK = ALPHA_MASK | DIGIT_MASK
• GRAPH_MASK = ALNUM_MASK | PUNCT_MASK

Superficially, you can also use ALPHA_MASK = UPPER_MASK | LOWER_MASK, but in some locales, there are alphabetic characters that are neither upper-case nor lower-case.

So, we can define masks as follows:

enum CTYPE_MASK {
    DIGIT_MASK = 0x0001,
    XDIGT_MASK = 0x0002,
    LOWER_MASK = 0x0004,
    UPPER_MASK = 0x0008,
    ALPHA_MASK = 0x0010,
    PUNCT_MASK = 0x0020,
    SPACE_MASK = 0x0040,
    PRINT_MASK = 0x0080,
    CNTRL_MASK = 0x0100,
    BLANK_MASK = 0x0200,

    ALNUM_MASK = ALPHA_MASK | DIGIT_MASK,
    GRAPH_MASK = ALNUM_MASK | PUNCT_MASK
};

extern unsigned short ctype_bits[];

The data for the character set; the data shown is for the first half of ISO 8859-1, but is the same for the first half of all the 8859-x code sets. I'm using C99 designated initializers as a documentary aid, even though the entries are all in order:

unsigned short ctype_bits[] =
{
    [EOF   +1] = 0,
    ['\0'  +1] = CNTRL_MASK,
    ['\1'  +1] = CNTRL_MASK,
    ['\2'  +1] = CNTRL_MASK,
    ['\3'  +1] = CNTRL_MASK,
    ['\4'  +1] = CNTRL_MASK,
    ['\5'  +1] = CNTRL_MASK,
    ['\6'  +1] = CNTRL_MASK,
    ['\a'  +1] = CNTRL_MASK,
    ['\b'  +1] = CNTRL_MASK,
    ['\t'  +1] = CNTRL_MASK|SPACE_MASK|BLANK_MASK,
    ['\n'  +1] = CNTRL_MASK|SPACE_MASK,
    ['\v'  +1] = CNTRL_MASK|SPACE_MASK,
    ['\f'  +1] = CNTRL_MASK|SPACE_MASK,
    ['\r'  +1] = CNTRL_MASK|SPACE_MASK,
    ['\x0E'+1] = CNTRL_MASK,
    ['\x0F'+1] = CNTRL_MASK,
    ['\x10'+1] = CNTRL_MASK,
    ['\x11'+1] = CNTRL_MASK,
    ['\x12'+1] = CNTRL_MASK,
    ['\x13'+1] = CNTRL_MASK,
    ['\x14'+1] = CNTRL_MASK,
    ['\x15'+1] = CNTRL_MASK,
    ['\x16'+1] = CNTRL_MASK,
    ['\x17'+1] = CNTRL_MASK,
    ['\x18'+1] = CNTRL_MASK,
    ['\x19'+1] = CNTRL_MASK,
    ['\x1A'+1] = CNTRL_MASK,
    ['\x1B'+1] = CNTRL_MASK,
    ['\x1C'+1] = CNTRL_MASK,
    ['\x1D'+1] = CNTRL_MASK,
    ['\x1E'+1] = CNTRL_MASK,
    ['\x1F'+1] = CNTRL_MASK,

    [' '   +1] = SPACE_MASK|PRINT_MASK|BLANK_MASK,

    ['!'   +1] = PUNCT_MASK|PRINT_MASK,
    ['"'   +1] = PUNCT_MASK|PRINT_MASK,
    ['#'   +1] = PUNCT_MASK|PRINT_MASK,
    ['$'   +1] = PUNCT_MASK|PRINT_MASK,
    ['%'   +1] = PUNCT_MASK|PRINT_MASK,
    ['&'   +1] = PUNCT_MASK|PRINT_MASK,
    ['\''  +1] = PUNCT_MASK|PRINT_MASK,
    ['('   +1] = PUNCT_MASK|PRINT_MASK,
    [')'   +1] = PUNCT_MASK|PRINT_MASK,
    ['*'   +1] = PUNCT_MASK|PRINT_MASK,
    ['+'   +1] = PUNCT_MASK|PRINT_MASK,
    [','   +1] = PUNCT_MASK|PRINT_MASK,
    ['-'   +1] = PUNCT_MASK|PRINT_MASK,
    ['.'   +1] = PUNCT_MASK|PRINT_MASK,
    ['/'   +1] = PUNCT_MASK|PRINT_MASK,

    ['0'   +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK,
    ['1'   +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK,
    ['2'   +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK,
    ['3'   +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK,
    ['4'   +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK,
    ['5'   +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK,
    ['6'   +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK,
    ['7'   +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK,
    ['8'   +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK,
    ['9'   +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK,

    [':'   +1] = PUNCT_MASK|PRINT_MASK,
    [';'   +1] = PUNCT_MASK|PRINT_MASK,
    ['<'   +1] = PUNCT_MASK|PRINT_MASK,
    ['='   +1] = PUNCT_MASK|PRINT_MASK,
    ['>'   +1] = PUNCT_MASK|PRINT_MASK,
    ['?'   +1] = PUNCT_MASK|PRINT_MASK,
    ['@'   +1] = PUNCT_MASK|PRINT_MASK,

    ['A'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK|XDIGT_MASK,
    ['B'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK|XDIGT_MASK,
    ['C'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK|XDIGT_MASK,
    ['D'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK|XDIGT_MASK,
    ['E'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK|XDIGT_MASK,
    ['F'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK|XDIGT_MASK,
    ['G'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['H'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['I'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['J'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['K'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['L'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['M'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['N'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['O'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['P'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['Q'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['R'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['S'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['T'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['U'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['V'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['W'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['X'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['Y'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,
    ['Z'   +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK,

    ['['   +1] = PUNCT_MASK|PRINT_MASK,
    ['\\'  +1] = PUNCT_MASK|PRINT_MASK,
    [']'   +1] = PUNCT_MASK|PRINT_MASK,
    ['^'   +1] = PUNCT_MASK|PRINT_MASK,
    ['_'   +1] = PUNCT_MASK|PRINT_MASK,
    ['`'   +1] = PUNCT_MASK|PRINT_MASK,

    ['a'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK|XDIGT_MASK,
    ['b'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK|XDIGT_MASK,
    ['c'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK|XDIGT_MASK,
    ['d'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK|XDIGT_MASK,
    ['e'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK|XDIGT_MASK,
    ['f'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK|XDIGT_MASK,
    ['g'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['h'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['i'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['j'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['k'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['l'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['m'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['n'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['o'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['p'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['q'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['r'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['s'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['t'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['u'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['v'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['w'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['x'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['y'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,
    ['z'   +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK,

    ['{'   +1] = PUNCT_MASK|PRINT_MASK,
    ['|'   +1] = PUNCT_MASK|PRINT_MASK,
    ['}'   +1] = PUNCT_MASK|PRINT_MASK,
    ['~'   +1] = PUNCT_MASK|PRINT_MASK,
    ['\x7F'+1] = CNTRL_MASK,

    ...continue for second half of 8859-x character set...
};

#define isalpha(c)  ((ctype_bits+1)[c] & ALPHA_MASK)
#define isupper(c)  ((ctype_bits+1)[c] & UPPER_MASK)
#define islower(c)  ((ctype_bits+1)[c] & LOWER_MASK)
#define isalnum(c)  ((ctype_bits+1)[c] & ALNUM_MASK)
#define isgraph(c)  ((ctype_bits+1)[c] & GRAPH_MASK)
#define isprint(c)  ((ctype_bits+1)[c] & PRINT_MASK)
#define iscntrl(c)  ((ctype_bits+1)[c] & CNTRL_MASK)
#define isdigit(c)  ((ctype_bits+1)[c] & DIGIT_MASK)
#define isblank(c)  ((ctype_bits+1)[c] & BLANK_MASK)
#define isspace(c)  ((ctype_bits+1)[c] & SPACE_MASK)
#define ispunct(c)  ((ctype_bits+1)[c] & PUNCT_MASK)
#define isxdigit(c) ((ctype_bits+1)[c] & XDIGT_MASK)

As already noted, the names here are actually in the namespace reserved for users, so if you looked in a <ctype.h> header you'd find more cryptic names and they'd probably all start with one or two underscores.

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.