§38  TEX82  PART 4: STRING HANDLING 19

38. String handling. Control sequence names and diagnostic messages are variable-length strings of eight-bit characters. Since Pascal does not have a well-developed string mechanism, TEX does all of its string processing by homegrown methods.

Elaborate facilities for dynamic strings are not needed, so all of the necessary operations can be handled with a simple data structure. The array str pool contains all of the (eight-bit) ASCII codes in all of the strings, and the array str start contains indices of the starting points of each string. Strings are referred to by integer numbers, so that string number s comprises the characters str pool [j] for str start [s] ≤ j < str start [s + 1]. Additional integer variables pool ptr and str ptr indicate the number of entries used so far in str pool and str start , respectively; locations str pool [pool ptr ] and str start [str ptr ] are ready for the next string to be allocated.

String numbers 0 to 255 are reserved for strings that correspond to single ASCII characters. This is in accordance with the conventions of , which converts single-character strings into the ASCII code number of the single character involved, while it converts other strings into integers and builds a string pool file.

Thus, when the string constant  appears in the program below,  converts it into the integer 46,
which is the ASCII code for a period, while  will convert a string like  into some integer greater

than 255. String number 46 will presumably be the single character ‘ ’; but some ASCII codes have no standard visible representation, and TEX sometimes needs to be able to print an arbitrary ASCII character, so the first 256 strings are used to specify exactly what should be printed for each of the 256 possibilities.

Elements of the str pool array must be ASCII codes that can actually be printed; i.e., they must have an xchr equivalent in the local character set. (This restriction applies only to preloaded strings, not to those generated dynamically by the user.)

Some Pascal compilers won’t pack integers into a single byte unless the integers lie in the range −128 . . 127. To accommodate such systems we access the string pool only via macros that can easily be redefined.

define si (#) ≡ # { convert from ASCII code to packed ASCII code }

define so(#) ≡ # { convert from packed ASCII code to ASCII code } ⟨ Types in the outer block 18 ⟩ +≡

pool pointer = 0 . . pool size; { for variables that point into str pool }

str number = 0 . . max strings ; { for variables that point into str start }

packed ASCII code = 0 . . 255; { elements of str pool array }

39. ⟨ Global variables 13 ⟩ +≡ str pool : packed array [pool pointer ] of packed ASCII code; { the characters } str start : array [str number ] of pool pointer ; { the starting pointers } pool ptr : pool pointer ; { first unused position in str pool } str ptr : str number ; { number of the current string being created } init pool ptr : pool pointer ; { the starting value of pool ptr } init str ptr : str number ; { the starting value of str ptr }

40. Several of the elementary string operations are performed using macros instead of Pascal procedures, because many of the operations are done quite frequently and we want to avoid the overhead of procedure calls. For example, here is a simple macro that computes the length of a string.

define length(#) ≡ (str start [# + 1] − str start [#]) { the number of characters in string number # }

41. The length of the current string is called cur length:

define cur length ≡ (pool ptr − str start [str ptr ])

20  PART 4: STRING HANDLING  TEX82 §42

42. Strings are created by appending character codes to str pool . The append char macro, defined here, does not check to see if the value of pool ptr has gotten too high; this test is supposed to be made before append char is used. There is also a flush char macro, which erases the last character appended.

To test if there is room to append l more characters to str pool , we shall write str room(l), which aborts TEX and gives an apologetic error message if there isn’t enough room.

define append char (#) ≡ { put ASCII code # at the end of str pool } begin str pool [pool ptr ] ← si (#); incr (pool ptr ); end

define flush char ≡ decr (pool ptr ) { forget the last character in the pool } define str room(#) ≡ { make sure that the pool hasn’t overflowed }

begin if pool ptr + # > pool size then overflow ( ␣ , pool size − init pool ptr ); end

43. Once a sequence of characters has been appended to str pool , it officially becomes a string when the function make string is called. This function returns the identification number of the new string as its value. function make string : str number ; { current string enters the pool }

begin if str ptr = max strings then overflow ( ␣ ␣ , max strings − init str ptr ); incr (str ptr ); str start [str ptr ] ← pool ptr ; make string ← str ptr − 1; end;

44. To destroy the most recently made string, we say flush string .

define flush string ≡ begin decr (str ptr ); pool ptr ← str start [str ptr ]; end

45. The following subroutine compares string s with another string of the same length that appears in buffer starting at position k; the result is true if and only if the strings are equal. Empirical tests indicate that str eq buf is used in such a way that it tends to return true about 80 percent of the time. function str eq buf (s : str number ; k : integer ): boolean; { test equality of strings }

label not found ; { loop exit } var j: pool pointer ; { running index }

result : boolean; { result of comparison } begin j ← str start [s]; while j < str start [s + 1] do

begin if so(str pool [j]) ≠ buffer [k] then begin result ← false; goto not found ; end;

incr (j); incr (k);

end; result ← true;

not found : str eq buf ← result ; end; 46. Here is a similar routine, but it compares two strings in the string pool, and it does not assume that they have the same length. function str eq str (s, t : str number ): boolean; { test equality of strings }

label not found ; { loop exit } var j, k: pool pointer ; { running indices }

result : boolean; { result of comparison } begin result ← false; if length(s) ≠ length(t) then goto not found ; j ← str start [s]; k ← str start [t]; while j < str start [s + 1] do

begin if str pool [j] ≠ str pool [k] then goto not found ; incr (j); incr (k); end;

result ← true; not found : str eq str ← result ;

end;

47. The initial values of str pool , str start , pool ptr , and str ptr are computed by the program, based in part on the information that has output while processing TEX.

init function get strings started : boolean;

{ initializes the string pool, but returns false if something goes wrong } label done, exit ; var k, l: 0 . . 255; { small indices or counters }

m, n: text char ; { characters input from pool file } g: str number ; { garbage } a: integer ; { accumulator for check sum } c: boolean; { check sum has been checked }

begin pool ptr ← 0; str ptr ← 0; str start [0] ← 0; ⟨ Make the first 256 strings 48 ⟩; ⟨ Read the other strings from the file and return true, or give an error message and return

false 51 ⟩; exit : end;

tini

48. define app lc hex (#) ≡ l ← #; if l < 10 then append char (l + ) else append char (l − 10 + )

⟨ Make the first 256 strings 48 ⟩ ≡

for k ← 0 to 255 do

begin if (⟨ Character k cannot be printed 49 ⟩) then begin append char ( ); append char ( ); if k < ´ 100 then append char (k + ´ 100 ) else if k < ´ 200 then append char (k − ´ 100 )

else begin app lc hex (k div 16); app lc hex (k mod 16);

end; end

else append char (k);

g ← make string ;

end

This code is used in section 47.

49. The first 128 strings will contain 95 standard ASCII characters, and the other 33 characters will be printed in three-symbol form like ‘ ’ unless a system-dependent change is made here. Installations that have an extended character set, where for example xchr [´ 32 ] = ´ ´ , would like string ´ 32 to be the single character ´ 32 instead of the three characters ´ 136 , ´ 136 , ´ 132 ( ). On the other hand, even people with an extended character set will want to represent string ´ 15 by , since ´ 15 is carriage return; the idea is to produce visible strings instead of tabs or line-feeds or carriage-returns or bell-rings or characters that are treated anomalously in text files.

Unprintable characters of codes 128–255 are, similarly, rendered – .

The boolean expression defined here should be true unless TEX internal code number k corresponds to a non-troublesome visible symbol in the local character set. An appropriate formula for the extended character set recommended in The TEXbook would, for example, be ‘k ∈ [0, ´ 10 . . ´ 12 , ´ 14 , ´ 15 , ´ 33 , ´ 177 . . ´ 377 ]’. If character k cannot be printed, and k < ´ 200 , then character k + ´ 100 or k − ´ 100 must be printable; moreover, ASCII codes [´ 41 . . ´ 46 , ´ 60 . . ´ 71 , ´ 141 . . ´ 146 , ´ 160 . . ´ 171 ] must be printable. Thus, at least 80 printable characters are needed. ⟨ Character k cannot be printed 49 ⟩ ≡

(k < ␣ ) ∨ (k > )

This code is used in section 48.

50. When the  system program called  processes the  description that you are now
reading, it outputs the Pascal program  and also a string pool file called  . The

program reads the latter file, where each string appears as a two-digit decimal length followed by the string itself, and the information is recorded in TEX’s string memory. ⟨ Global variables 13 ⟩ +≡

init pool file: alpha file; { the string-pool file output by }

tini

51. define bad pool (#) ≡ begin wake up terminal ; write ln(term out , #); a close(pool file); get strings started ← false; return; end

⟨ Read the other strings from the file and return true, or give an error message and return

false 51 ⟩ ≡ name of file ← pool name; { we needn’t set name length } if a open in(pool file) then

begin c ← false;

repeat ⟨ Read one string, but return false if the string memory space is getting too tight for

comfort 52 ⟩; until c; a close(pool file); get strings started ← true; end

else bad pool (´ ␣ ␣ ´ ´ ␣ ␣ ´ )

This code is used in section 47.

52. ⟨ Read one string, but return false if the string memory space is getting too tight for comfort 52 ⟩ ≡ begin if eof (pool file) then bad pool (´ ␣ ␣ ␣ ␣ ␣ ´ ); read (pool file, m, n); { read two digits of string length } if m = ´ ´ then ⟨ Check the pool check sum 53 ⟩ else begin if (xord [m] < ) ∨ (xord [m] > ) ∨ (xord [n] < ) ∨ (xord [n] > ) then

bad pool (´ ␣ ␣ ␣ ´ ´ ␣ ␣ ␣ ␣ ´ ); l ← xord [m] ∗ 10 + xord [n] − ∗ 11; { compute the length } if pool ptr + l + string vacancies > pool size then bad pool (´ ␣ ␣ ␣ ␣ ␣ ´ ); for k ← 1 to l do

begin if eoln(pool file) then m ← ´ ␣´ else read (pool file, m); append char (xord [m]); end;

read ln(pool file); g ← make string ;

end; end

This code is used in section 51.

53. The  operation $ denotes the value that should be at the end of this  file; any other

value means that the wrong pool file has been loaded. ⟨ Check the pool check sum 53 ⟩ ≡

begin a ← 0; k ← 1; loop begin if (xord [n] < ) ∨ (xord [n] > ) then

bad pool (´ ␣ ␣ ␣ ␣ ´ ´ ␣ ␣ ␣ ´ ); a ← 10 ∗ a + xord [n] − ; if k = 9 then goto done; incr (k); read (pool file, n); end;

done: if a ≠ $ then bad pool (´ ␣ ␣ ´ ´ ␣ ␣ ␣ ␣ ´ ); c ← true; end

This code is used in section 52.