Programmer 7500/MAX_PROGRAMMERS.iso/INFO/C/ONE_ON_9.ZIP/ONE_ON_9.DOC

Text File | 1988-03-07 | 18.1 KB | 309 lines

   This text is taken from an article by Jean-Pierre Schachter called DATA
STRUCTURES AND SCROLLING. It appeared in the February 1987, Volume 4, Num-
ber 2, issue of Computer Language.

                            Start of text:
------------------------------------------------------------------------------
   As users of MS-DOS know, the operating system contains programmer-ac-
cessible system calls (interrupt 0x10, numbers 6 and 7) for scrolling the
screen. In fact, these interrupts are of limited usefulness since the
scrolling is not buffered and only vertical. While the interrupt could be used
even with a buffered arrangement in which one's text does not disappear
permanently off the edge of the screen, it is much simpler to ignore it
entirely and write one's own scrolling routine.
   While a program called One_On_Nine has the practical objective of demon-
strating a specific algorithm, it also has the more general and theoretical
objective of illustrating the use of superimposed and noncontiguous data
structures. Since understanding the latter will be helpful in commenting on
One_On_Nine, I'll start by discussing them.

SUPERIMPOSED AND NONCONTIGUOUS
   Beginning programmers tend to imagine arrays as extended in three-dimen-
sional space; needless to say, they begin to have trouble with arrays
dimensioned n > 3. They also tend to think of memory allocations as unique in
their structures, each having, necessarily, only one structure. These
assumptions are constricting and lead to unnecessarily complicated program-
ming.
   It is liberating to discover that no matter how complex the data structure
in a declaration or a programmer's mind, in the machine it's just a linear
sequence of contiguous bytes. What makes an array an array is the complex
incrementation automatically implemented by a high-level language that lets
one step through this linear sequence in a regular and predetermined way.
   The machinery that makes this incrementation possible is invisible to
the user who is given information only on a need-to-know basis. While lower-
level languages also provide the invisible incrementation devices, in addition
they give the programmer the tools to construe and reconstrue his or her data
any which way he or she can. Two useful examples of creativity in data
structuring involve whae I call superimposed data structures and noncontiguous
data structures.
   If a language provides a way of declaring a data pattern without a sim-
ultaneous allocation of memory, then the way is usually clear for deciding
where in memory the pattern is to begin. This implies that the same physical
region of memory can be treated as having more than one structure. A given
region of memory can, for example, be treated at one time as a collection of
chars or bytes and at another as a collection of ints.
   Were this all, this principle would be merely of mild interest, but it
works with declared data types as well as those that come native to the
language. Thus in C the ability to declare structs and unions provides the
means for superimposing different data patterns on one in an unlimited num-
ber of ways.
   While this capability is native to C, it can also be found in an extrem-
ely convenient form as an extension of standard Pascal in Turbo Pascal, the
Borland International implementation. Not only does Turbo allow for pointers
but also for the declaration of variables at specified addresses, which in
turn allows for the superimposition of data sturctures. Later we will see how
this works in C.
   While superimposition counteracts the superstition that a given region
of memory is what it was declared and not something else, another liberation
still has to take place: liberation from the belief that separated or
noncontiguous regions of memory may never come together into one data
structure. It is true that memory made available by the alloc() family of
functions and by array declarations consists of contiguous blocks of RAM, but
these are not the only ways of dealing with memory. When data structures are
created by means of arrays of pointers that subsequently are initialized, any
region can become unified with any other. (This will be shown in the code.)

ONE_ON_NINE
   The objective of One_On_Nine is to create a virtual screen in memory
that is nine times the size of the visible portion of the acrual display. The
virtual memory is best imagined as a tic-tac-toe grid that initially has its
central panel mapped one to one with the visible display (more precisely, one
to two). The problem faced in dealing with this virtual screen is that the
subportion of the allocated memory we wish to manipulate is not itself a
contiguous, linear sequence of bytes (Figure 1).


SUBPORTION'S NONCONTIGUOUS SEQUENCE:

Beginning of allocation
A|----------------------------------------------------------| ----
 |                                              ^           |D  ^
 |<----------------------240 bytes--------------|---------->|   |
 |                                              |           |   |
 |                                              | 25        |   |
 |                   B                   C      |           |   |
 |                   |-------------------| -----\/          |   |
 |                   |                   |      ^           |   |
 |<----80 bytes----->|<----80 bytes----->|      |           |   |
 |                   |                   |      | 25        |   | 75
 |                   |                   |      |           |   |
 |                   |                   |      |           |   |
 |                   |-------------------| -----\/          |   |
 |                                                          |   |
 |                                                          |   |
 |                                                          |   |
 |                                                          |   |
 | B is located at A + ((240*25) + 80)                      |   |
 |                                                          |   |
 |----------------------------------------------------------| --\/
                                                             E

                  ******* FIGURE 1 *******

   In Figure 1, the region from A to E is allocated to the pointer pb and
consists  of a contiguous sequence of bytes. We are interested, however, in
having efficient access to 25 noncontiguous sequences within that allocation,
namely the 25 strings between the columns B and C, which are separated from
each other by memory between A and B and between C and D. It should be clear
that no array making direct reference to memory can solve this problem.
   The strategy of One_On_Nine is to declare an array of 25 pointers, each
of which is initialized to one of the 25 addresses immediately below B. By
shifting these addresses systematically, different 25-by-80 sections of the
larger virtual screen can be accessed. When the program is run, it begins by
filling the display with alpha garbage for display purposes. It then waits for
input. Acceptable input is limited to the arrow keys, the escape key, with all
other keys yielding BEEP. As one would expect, the arrow keys allow the user
to scroll in any direction within the limits of the 75-by-240 grid.
   The code for One_On_Nine was written in Microsoft C and may have two un-
familiar features. (The code also compiles in Quick C -typist)  First, the
Microsoft compiler allows for the creation of pointers to segments beyond the
128K mark (far pointers), a real convenience when dealing with screen memory
that begins (under MS-DOS and with a composite monitor at 0xb8000, and with a
monochrome monitor at 0xb0000). Second, a quick look at the function
get_scan() will show that it makes use of an interrupt calling function that
is fairly common but not System V.  (I wrote get_scan() for user input because
I wanted access to the arrow key scan codes as well as a non-echoing input
requiring no <cr>. The ability to recognize the arrow keys, however, is not
essential to the program and need not detain us; I'll comment later on the use
of far pointers.)
   After the macros and headers, One_On_Nine starts its declarations. First,
notice how few there are; second, notice how simple they are. There are only
two global declarations: *pb, a pointer to char that points to the virtual
screen, and line[], a 25-element array of pointers to char that will be the
basis of our mapping from virtual screen to visible display.
   The main() module of One_On_Nine contains very little beyond function
calls. The static char array clrscr[] provides the ANSI screen-clearing string
for the macro CLRSCR. The clrscr[] declaration is of interest only because it
illustrates how an initialized static array can be used to hold a string
constant containing unprintable characters in a program. In One_On_Nine, the
unprintable character was the escape required for the ANSI clear-screen
sequence.
   Aside from the screen-clearing code, the only other line that is not a
simple function call is (the memset() call), which simulaneously allocates
18,000 bytes and sets it to blanks.

MOVE IT
   The central function in One_On_Nine is the brief move_it() function.
Move_it() sets the addresses in the pointer array line[], which is also used
by the function show_it(). Show_it() is the function that copies the
designated rectangle from the linear memory pointed by pb to the display. It
is line[] then that holds the starting addresses of the 25  80-element
regions; show_it() simply uses those addresses to find it's material for 25
copies.
   The system is primed by setting line[]'s sddresses to the central rectan-
gle by means of a move_it() call on pb plus 6080 (the upper left-hand corner
of the central rectangle region, 6080 being equal to (25*240) + 80). After
this, the arrow keys are used simply to increment or decrement pb with a call
to move_it(), thereby shifting the mapping between display and virtual screen.
Given that the heart of the action lies in move_it(), this function warrants
closer inspection.
   Move_it() does something interesting. So far we have been concentrating
simply on the use of pointer arrays in the accessing of noncontiguous memory
blocks. This device can be greatly enhanced by using suitably defined structs
and pointer arithmetic. The feature of the struct that we tap in move_it() is
that incrementation on a pointer to a struct is based on the size of the
scruct itself; this means we have a very neat way of setting step sizes for
stepping through a region of memory.
   As already mentioned, move_it() initializes the pointer array line[]; we
are now in a position to see how it does this. While the call to move_it()
uses pb (declared as a pointer to char), the parameter of move_()--start--
is declared a pointer to a struct, gapl. Gapl's sole element is an array of
240 chars. You must remember that in this case only memory for a local pointer
has been allocated.
   In a call to move_it(), start gets it's initial (address) value from
pb, assigns it to line[0], and then cycles through buffer[] in 240 char hops,
leaving it's pb address in the next element of line[] each time it touches
down. The new addresses in line[] are then used by show_it() to refresh or
update the display.
   It should also be noted that the reason for using register variables in
move_it(), as well as some of the other functions, lies in the need for
execution speed. When execution is slow, lateral scrolling can show an
unpleasant wave through the display as the screen is refreshed from top to
bottom. With the machine running at 8 Mhz, One_On_Nine shows almost no wave,
though at 4.77 MHz the wave is visible.

SHOW IT
   While move_it() is the function at the heart of One_On_Nine, show_it()
also deserves discussion because it illustrates how a direct memory-to-memory
swap is possible between a buffer and the screen.
   The problem in such a swap lies in addressing high memory, in this case
memory beginning at 0xb0000, and initializing a pointer to that memory. Whether
and how this can be done depends on the specific compiler used. The Microsoft
compiler has two ways: using the large-memory model or using a far pointer.
   Show_it() uses the second method and also demonstrates an elegant tech-
nique of initialization. The first thing to understand is that while far
pointers use 32 bits instead of the usual 16, they do not resemble long ints
but rather a two-cell array of ints. Because of MS-DOS's use of segment-offset
arithmetic in it's addressing, the far pointer requires the segment address in
it's left 16 bits and the offset in it's right 16 bits. Unless one is
attempting to reach a byte at an address that is not a multiple of 16, one can
leave the offset at 0 and set the segment to the actual address desired
divided by 16.
   Since 0xb0000 (720,896) is a multiple of 16 (720,896/16 = 45,056), all we
need do to initialize the far pointer is put 45,056 (0xb000) into it's left 16
bits. Since the shift operation leaves 0's behind as it shifts a bit pattern,
the code << 16 in show_it() manages in one move to initialize both of the far
pointer's sides, the segment and the offset.
   The standard way of doing this with the Microsoft compiler is to use the
provided macros FP_SEG() and FP_OFF(). For example, if the far pointer was
named distant and the address was 0xb0000, the two lines:

FP_SEG(distant) = 0xb000;
FP_OFF(distant) = 0;

would place 0xb000 in distant's segment cell and 0 in it's offset cell.
   The other thing to notice about show_it() is that the device of declaring
pointers to structures is used again, once to shift lines but also once to
skip over bytes. The latter is necessary because one page of screen memory is
actually twice the size of the rectangle we have defined within the virtual
screen. The reason for this is that each byte of screen memory has a companion
that sets the displayed byte's attributes (such as intensity, blinking,
reverse, etc.) and must be skipped before reaching the next visible byte. The
rest of show_it() simply works its way through the virtual rectangle and
display memory by incrementing the pointers to structs.
   We can now see how superimposed and noncontiguous data structures can be
used. It should be clear that in One_On_Nine a simulated array is continually
moved around over the surface of a much larger character array. It should also
be clear that the array being moved is itself noncontiguous, since it consists
for all practical purposes of 24 discrete 80-element char strings. We have
been moving a noncontinuous array over the surface of another, larger array.

SPECIAL CASES AND FUNCTIONS
   But while the kinds of data structure I have been describing add consid-
erable power to the programmer's arsenal, it must be pointed out that with
regular use a need arises for a specialized set of supporting functions. Since
these structures are all based on the use of pointer arrays, functions are
wanted that take pointer arrays as their parameters but operate on the values
pointed to by their elements, not the arrays.
   The common C function puts(char*), for example, takes a pointer to char as
it's parameter, the pointer pointing to the beginning of a string of
characters in memory. What if, however, we did not have a contiguous sequence
of characters to output but rather a sequence of characters at various loca-
tions listed by their addresses in an array ?
   These two cases are compared here. Case 1 is puts(). Case 2 requires a
function that cycles through an array of pointers, putting out the content at
the address contained in each successive cell of the array:
 Case 1.  Go to add1, then output what is contained there. Do this for each
successive add until it's contained char is \0:

add1 [address of the beginning of the character array]
C | A | T | \0

Case 2. Go to add1, then output what is contained at the address in add1,viz.
[ADD1]. Do this for each successive add until you reach addn:

add1 [the beginning of the pointer array]
[ADD1] | [ADD2] | [ADD3]
  C    |   A    |   T

   The function ptr_puts() below does exactly this:

#define NEW_LINE; putchar(13);
   putchar(10)
ptr_puts(ptray, chnum)
struct ptopt {
   char *ptchr;
} *ptray;
int chnum;
{
   while(chnum--)
      putchar(*(ptray++)->ptchr);
   NEW_LINE;
}

while the following function, ptr_cpy(), is a pointer-array version of the
common function strncpy(string1, string2, n), which works on character arrays:

ptr_cpy(dest, origin, chnum)
struct oneptr {
   char *ptchar;
} *dest, *origin;
int chnum;
{
   while (chnum--)
      *(dest++)->ptchar = *(origin++)->ptchar;
   NEW_LINE;
}

   The only tricky thing about these functions is that they declare the
incoming pointer array as a pointer-to-pointer to char, which allows for
incrementing on the array addresses while at the same time giving access to
the data pointed to by each element of the array being incremented. Without
the pointer-to-pointer declaration, increminting and decrementing would take
place on the address of the first data element, which is not what is wanted.
What is wanted is incrementation through the array holding the addresses,
which is what one gets in ptr_puts() and ptr_cpy().
   Put in terms of Case 2, the code must be written in such a way that the
pointer is incremented on add1, not [ADD1]. There is no telling what is con-
tained in [ADD1]++, but in add1++ we can find the next pointer to the next
char we wish to put to screen. The function ptr_puts() writes to display the
values pointed to by each element of a pointer array. On the other hand,
ptr_cpy() copies the values pointed to by one pointer array's elements to the
memory locations pointed to by another pointer array's elements.
   For applications making regular use of pointer arrays, one would probably
want to develop a library of such functions closely paralleling the functions
known to be useful for dealing with straightforward linear arrays.

                           End of text
----------------------------------------------------------------------------