TweetFollow Us on Twitter

Apr 95 Challenge
Volume Number:11
Issue Number:4
Column Tag:Programmer’s Challenge

Programmer’s Challenge

By Mike Scanlin, Mountain View, CA

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

Stock Market Database

This month’s Challenge is to write a piece of code that records stock market trades and then allows you to query it to find out price and volume information for a particular stock at a particular time. This code could be the core of a much larger stock analysis program (and it would likely be the bottleneck).

The typedefs you will use are:

typedef unsigned char uchar;
typedef unsigned long ulong;

typedef struct TimeStamp {
 uchar  yearsFrom1900;
 uchar  month;
 uchar  day;
 uchar  hour;
 uchar  minute;
 uchar  second;
} TimeStamp;

typedef char Str7[8];

typedef struct Trade {
 Str7   symbol;
 TimeStamptime;
 Fixed  price;
 ulong  numShares;
} Trade;

The four routines you’ll write are:

void *
InitTradeDatabase(maxRAM)
ulong   maxRAM;

void
NewTrade(privateDataPtr, trade)
void    *privateDataPtr;
Trade   trade;

Fixed
PriceIs(privateDataPtr, symbol, time);
void    *privateDataPtr;
Str7    symbol;
TimeStamp time;
ulong
VolumeIs(privateDataPtr, symbol, time);
void    *privateDataPtr;
Str7    symbol;
TimeStamp time;

InitTradeDatabase is called once before any other functions. It is untimed (i.e. it doesn’t matter if it’s slow to execute) and should return a pointer to your database’s private data (which is passed to the other 3 routines as privateDataPtr). MaxRAM is the largest amount of RAM that your code can use (in bytes); it will be between 512K and 4MBs. You can also use up to 50MBs of disk space.

Once InitTradeDatabase has been called, the other 3 routines will be called pseudo-randomly many times. The only restriction is that each time NewTrade is called, the trade’s time will be later than all previous trades. You can think of NewTrade being called once for each trade that occurs, as it occurs (like the data flowing across a ticker tape, which happens in chronological order).

The chronological sequence of NewTrade calls will be interspersed with calls to PriceIs and VolumeIs. PriceIs returns the price of a given stock at or before the given time. If you are asked for the price of a stock at a time before you have any trade data for that stock then return a price of zero.

VolumeIs returns the daily volume of a given stock as of a given time on that day. For example, if the time is 2/28/95 at 11am then VolumeIs should return the sum of all trades’ numShares that occurred on the 28th of February, 1995, before 11am (and excluding trades that occurred at exactly 11am).

Taken together these routines will allow someone to produce price/volume graphs for a stock of their choice (once they’ve fed it lots of trade data).

Here are some examples. A time of 13:32:15 (15 seconds past 1:32pm) on Mar 2nd, 1995, is:

 yearsFrom1900 = 95;
 month = 3;
 day = 2;
 hour = 13;
 minute = 32;
 second = 15;

A price of 14 and 11/16ths would be:

 price = 0x000EB000; /* 14.6875 */

Remember, a Fixed is 16 bits of integer (0x000E) and 16 bits of fraction (0xB000). You can think of it as a 32 bit integer that you could divide by 216 to get the floating point equivalent. The value 1 is 0x00010000. The value 0.5 is 0x00008000. Stock prices are normally quoted in 1/2s, 1/4s, 1/8s, 1/16ths, 1/32nds and 1/64ths, and those are the only possible fractions your code will receive.

Symbols are uppercase, 7 character PStrings. The symbol for Apple Computer is AAPL. It would be:

 
 Str7 symbol;
 symbol[0] = 4; /* length */
 symbol[1]=‘A’; symbol[2]=‘A’; symbol[3]=‘P’; symbol[4]=‘L’;

NumShares is always greater than zero and will only very rarely be larger than 100,000 (the max, for our purposes, is 10,000,000).

Note that, on a typical day, the stock exchanges of the world have hundreds of thousands of transactions. It is all but certain that your routine will run out of RAM. You will need to be prepared to swap some trade data to disk. And then you need an efficient way to retrieve that data if you are asked for price or volume information once you’ve swapped it to disk. Part of this Challenge is to come up with a clever way to store RAM indexes of disk-based trade data. And you’ll probably want to cache at least some (if not all) of the trade data in RAM when you can. You will not be given more than 10MB of trade data (since you can use 50MB of disk space, you should be fine).

Write to me if you have any questions. Happy trading.

Two Months Ago Winner

Congratulations to Gustav Larsson (Mountain View, CA) for winning the Symbolize Challenge. Last month, Gustav was complimented for his small code that was only slightly slower than the winner. This month he has the largest code, but it’s almost 3x faster than the nearest competitor.

Here are the times and code sizes for each entry. Numbers in parens after a person’s name indicate that person’s cumulative point total for all previous Programmer Challenges, not including this one (see Top 20 chart below for info on the new cumulative point total plan):

Name time code

Gustav Larsson (10) 74 2942

Paul Hoffman 197 2100

Scott Manjourides 205 1972

Mason Thomas 235 1742

David Salmon 239 946

Dave Darrah (26) 249 1392

David Wiser 355 1492

Gustav’s solution is extremely nice code. It’s well thought out (good algorithms), well implemented (he knows his compiler) and well commented. If all of the authors of my favorite applications took as much care at crafting their code, then I’m sure I’d get at least an extra half hour of work done each day. I highly recommend that you study his code and comments.

Top 20 Contestants of All Time

This month marks the 32nd installment of the Programmer’s Challenge in MacTech. Prompted by Bob Boonstra’s retirement in February, I decided I needed to have some way to recognize past entrants who had done well. Thus was born the Top 20 Of All Time Chart.

Here’s how it works. There are three ways to earn points: (1) by scoring in the top 5 of any particular challenge, (2) by being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a challenge that I use. The points you can win are:

1st place 20 points

2nd place 10 points

3rd place 7 points

4th place 4 points

5th place 2 points

finding bug 5 points

suggesting challenge 2 points

Each month I will present the cumulative point totals for the top 20 contestants. It took me a while to compile the point totals for this month’s chart. I may have made a mistake. If you think you deserve more points than I’ve given you, please write to me and explain why (i.e. give me a list the months you finished in the top 5 as well as the months you found a bug or suggested a challenge I used and I’ll check it out). If your name is not in the current Top 20 but you want to know how many points you have, then e-mail me and I’ll tell you. Note that the numbers below include points awarded for this months’ top 5 entrants.

So, here it is. Congrats, everyone, on the hard work it took to get here! (Note: ties are listed alphabetically by last name -- there are 23 people listed this month because 7 people had 20 points each.)

Top 20 Contestants of All Time

1. Boonstra, Bob 176

2. Karsh, Bill 71

3. Stenger, Allen 65

4. Cutts, Kevin 56

5. Riha, Stepan 51

6. Goebel, James 49

7. Munter, Ernst 48

8. Nepsund, Ronald 40

9. Vineyard, Jeremy 40

10. Larsson, Gustav 30

11. Landry, Larry 29

12. Mallet, Jeff 27

13. Darrah, Dave 26

14. Elwertowski, Tom 24

15. Kasparian, Raffi 22

16. Lee, Johnny 22

17. Anderson, Troy 20

18. Burgoyne, Nick 20

19. Galway, Will 20

20. Israelson, Steve 20

21. Landweber, Greg 20

22. Noll, Bob 20

23. Pinkerton, Tom 20

Here is Gustav’s winning solution:

Symbolize.c

Copyright © 1995 Gustav Larsson

/*  Three areas of this program have been optimized: memory allocation, file I/O, and the symbol parse/convert 
algorithms.  Memory allocation and file I/O together typically use up 70-80% of the total execution time.  
Tuning these areas is tricky because so much is out of our control.  Factors such as the state of the disk 
cache and the heap can affect overall execution time by 10%, completely swamping many optimizations 
in the parse/convert algorithms.  Still, I have heavily optimized the parse/convert algorithms because that 
was the fun part of writing the program.  Limitations: - This program will not tolerate blank lines in the   input 
file or symbol file (a final carriage-return   is okay).  - Symbols names longer than about 2K may sometimes 
  cause the output buffer to be overrun, trashing memory.  This seems like a more-than-reasonable limit, 
even for mangled C++ names. */

#pragma options(pack_enums) /* required by <Memory.h> */

#include <stdio.h>
#include <Memory.h>


typedef unsigned char uchar;
typedef unsigned short ushort;
typedef unsigned long ulong;

#define CEILING(value,n) (n*(((value)+n-1)/n))

/* There is a substantial performance hit if a write exceeds the disk cache.  Large buffers also take longer 
to allocate via NewPtr.  Any buffer size between 8K and 16K seems to produce comparable results.  The 
actual buffer size here is 16K, to allow the contents to run over the 14K threshold. */

#define OUTPUT_BUFSIZE (16*1024)
#define OUTPUT_THRESHOLD (14*1024)

ishex

/* ishex[] indicates which ASCII characters are valid hex digits (0-9, A-F, a-f).  There are entries for all 256 
character codes since anything could be in the input file.*/

static uchar ishex[] = {
  0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,   /* 00-0F */
  0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,   /* 10-1F */
  0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,   /* 20-2F */
  1,1,1,1,1,1,1,1, 1,1,0,0,0,0,0,0,   /* 30-3F */
  0,1,1,1,1,1,1,0, 0,0,0,0,0,0,0,0,   /* 40-4F */
  0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,   /* 50-5F */
  0,1,1,1,1,1,1,0, 0,0,0,0,0,0,0,0,   /* 60-6F */
  0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,   /* 70-7F */
  0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,   /* 80-8F */
  0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,   /* 90-9F */
  0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,   /* A0-AF */
  0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,   /* B0-BF */
  0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,   /* C0-CF */
  0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,   /* D0-DF */
  0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,   /* E0-EF */
  0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0    /* F0-FF */
};

hexFromChar

/* hexFromChar[] converts a single hex character to its binary value.  Since this table is only used the character 
is known to be a hex digit, we can end the table at 'f'. */

static uchar hexFromChar[] = {
  0, 0, 0, 0, 0, 0, 0, 0,  0,0,0,0,0,0,0,0,   /* 00-0F */
  0, 0, 0, 0, 0, 0, 0, 0,  0,0,0,0,0,0,0,0,   /* 10-1F */
  0, 0, 0, 0, 0, 0, 0, 0,  0,0,0,0,0,0,0,0,   /* 20-2F */
  0, 1, 2, 3, 4, 5, 6, 7,  8,9,0,0,0,0,0,0,   /* 30-3F */
  0,10,11,12,13,14,15, 0,  0,0,0,0,0,0,0,0,   /* 40-4F */
  0, 0, 0, 0, 0, 0, 0, 0,  0,0,0,0,0,0,0,0,   /* 50-5F */
  0,10,11,12,13,14,15                         /* 60-66 */
};

charsFromInt

/* charsFromInt[] converts a binary value (0..99) to a pair of decimal digits.  The ULTOA macro converts 
two digits at a time. */

static ushort charsFromInt[] = {
  '00','01','02','03','04','05','06','07','08','09',
  '10','11','12','13','14','15','16','17','18','19',
  '20','21','22','23','24','25','26','27','28','29',
  '30','31','32','33','34','35','36','37','38','39',
  '40','41','42','43','44','45','46','47','48','49',
  '50','51','52','53','54','55','56','57','58','59',
  '60','61','62','63','64','65','66','67','68','69',
  '70','71','72','73','74','75','76','77','78','79',
  '80','81','82','83','84','85','86','87','88','89',
  '90','91','92','93','94','95','96','97','98','99'
};


void Symbolize( FILE *inputFile, FILE *symbolFile,
                FILE *outputFile, unsigned short symLength);

static unsigned short parseSymbols( char *buffer,
                char **name, ulong *value );

static void convert( char *inputBuffer, char *outputBuffer,
             char **symbolName, ulong *symbolValue,
             ushort numSymbols, ushort symLength,
             size_t inputLength, FILE* outputFile );

Symbolize

void Symbolize( FILE *inputFile, FILE *symbolFile,
                FILE *outputFile, unsigned short symLength)
{
  char *memory, *inputBuffer, *symbolBuffer, *outputBuffer;
  char **symbolName;
  size_t inputMax, symbolFileMax, len;
  ushort maxSymbols, numSymbols;
  ulong *symbolValue;

/* Compute buffer sizes, making them as tight as possible.  Round up for alignment.
Up to 9 characters can be added to the input buffer ("\r00000000").  See convert().  Up to 2 characters can 
be added to the  symbol file buffer ("\r\0").  The shortest possible line in the symbol file is 11 characters ("12345678 
A\r").  Also, reserve room for one extra symbol since the last one gets duplicated; see parseSymbols().  
 */

  inputMax = CEILING( inputFile->len + 9, 4 );
  symbolFileMax = CEILING( symbolFile->len + 2, 4);
  maxSymbols = symbolFile->len / 11 + 1;

  /* Grab all the memory in one call to NewPtr, then parcel it out.  This one call usually takes about 50% of 
the total execution time, at least on my machine.   */

  memory = NewPtr( inputMax + symbolFileMax + OUTPUT_BUFSIZE
  + (sizeof(char*) + sizeof(ulong*)) * maxSymbols );

  if ( !memory )
    return; /* at least the machine won't crash */

  inputBuffer = memory;
  symbolBuffer = inputBuffer + inputMax;
  outputBuffer = symbolBuffer + symbolFileMax;
  symbolName = (char **)( outputBuffer + OUTPUT_BUFSIZE );
  symbolValue = (ulong *)( symbolName + maxSymbols );

  /* Put files into binary mode.  This can reduce execution time by 20-40% for this program.  Setting files to 
binary mode should really be done at fopen().   */

  inputFile->binary =
  symbolFile->binary =
  outputFile->binary = 1;

  /* Read the symbol file.  Add a final '\r' if necessary.  Parse it, filling in symbolName[] and symbolValue[]. 
  */

  len = fread( symbolBuffer, 1, symbolFileMax, symbolFile );
  if ( symbolBuffer[ len-1 ] != '\r' )
    symbolBuffer[ len++ ] = '\r';
  symbolBuffer[ len ] = '\0';

  numSymbols = parseSymbols( symbolBuffer, symbolName,
                                              symbolValue );
                                              
  /* Read the input file.  Add a file '\r' if necessary.  
      convert() will write the output file.*/

  len = fread( inputBuffer, 1, inputMax, inputFile );
  if ( inputBuffer[ len-1 ] != '\r' )
    inputBuffer[ len++ ] = '\r';

  convert( inputBuffer, outputBuffer,
           symbolName, symbolValue,
           numSymbols, symLength,
           len, outputFile );

  /* Deallocate memory.   */

  DisposePtr( memory );
}


/* I had a great deal of trouble getting Think C to store pointer variables in registers.  An address register 
would sometimes remain allocated even after it went out of scope (this didn't happen with data registers). 
 In desperation, I created a single char* register variable that gets passed into various macros.  When repeatedly 
accessing an array, the first access below is slightly faster:
 *
 *    int array[10];
 *    register int *parray = array;
 *    foo = parray[i];  <-- slightly faster
 *    foo = array[i];
 *
 * Here are some casts for the shared address register: */

#define TEMP_UC ((uchar*)temp)
#define TEMP_US ((ushort*)temp)
#define TEMP_UL ((ulong*)temp)

XTOUL 

/* XTOUL converts ASCII hex (X) to an unsigned long (UL).  Ptr gets bumped past the 8 hex digits. */

#define XTOUL(ptr,result,temp)  \
{                               \
  register ulong _value;        \
                                \
  temp = (char*) hexFromChar;   \
  _value = TEMP_UC[ *ptr++ ];   /* nybble 7 (high) */ \
  _value <<= 4;                 \
  _value += TEMP_UC[ *ptr++ ];  /* nybble 6 */ \
  _value <<= 4;                 \
  _value += TEMP_UC[ *ptr++ ];  /* nybble 5 */ \
  _value <<= 4;                 \
  _value += TEMP_UC[ *ptr++ ];  /* nybble 4 */ \
  _value <<= 4;                 \
  _value += TEMP_UC[ *ptr++ ];  /* nybble 3 */ \
  _value <<= 4;                 \
  _value += TEMP_UC[ *ptr++ ];  /* nybble 2 */ \
  _value <<= 4;                 \
  _value += TEMP_UC[ *ptr++ ];  /* nybble 1 */ \
  _value <<= 4;                 \
  _value += TEMP_UC[ *ptr++ ];  /* nybble 0 (low) */ \
  result = _value;              \
}

ULTOA 

/* ULTOA converts an unsigned long (UL) to ASCII decimal (A) two digits at a time.  Buffer should be an array 
of 5 ushorts and will be filled with the right-justified ASCII digits (2 chars per ushort).  Length will be set to 
the number of digits.  This code is optimized for the common case of just a few digits.  / and % are inlined 
for 16-bit operands but generate a function call for 32-bit operands (except on a 68020 or better). */

#define TEN_TO_THE_4th 10000
#define TEN_TO_THE_5th 100000
#define TEN_TO_THE_6th 1000000
#define TEN_TO_THE_7th 10000000
#define TEN_TO_THE_8th 100000000
#define TEN_TO_THE_9th 1000000000

#define ULTOA(value,buffer,length,temp)           \
{                                                 \
  temp = (char*) charsFromInt;                    \
                                                  \
  if ( value < 100 )                              \
  {                                               \
    register ushort sval = value;                 \
    buffer[4] = TEMP_US[ sval ];                  \
    length = ( sval < 10 ? 1 : 2 );               \
  }                                               \
  else if ( value < TEN_TO_THE_4th )              \
  {                                               \
    register ushort sval = value;                 \
    buffer[4] = TEMP_US[ sval%100 ];              \
    buffer[3] = TEMP_US[ sval/100 ];              \
    length = ( sval < 1000 ? 3 : 4 );             \
  }                                               \
  else if ( value < TEN_TO_THE_6th )              \
  {                                               \
    register ushort sval = value % 10000;         \
    buffer[4] = TEMP_US[ sval%100 ];              \
    buffer[3] = TEMP_US[ sval/100 ];              \
    buffer[2] = TEMP_US[ value/10000 ];           \
    length = ( value < TEN_TO_THE_5th ? 5 : 6 );  \
  }                                               \
  else if ( value < TEN_TO_THE_8th )              \
  {                                               \
    register ushort sval = value % 10000;         \
    buffer[4] = TEMP_US[ sval%100 ];              \
    buffer[3] = TEMP_US[ sval/100 ];              \
    sval = value / 10000;                         \
    buffer[2] = TEMP_US[ sval%100 ];              \
    buffer[1] = TEMP_US[ sval/100 ];              \
    length = ( value < TEN_TO_THE_7th ? 7 : 8 );  \
  }                                               \
  else                                            \
  {                                               \
    register ushort sval = value % 10000;         \
    buffer[4] = TEMP_US[ sval%100 ];              \
    buffer[3] = TEMP_US[ sval/100 ];              \
    sval = (value / 10000) % 10000;               \
    buffer[2] = TEMP_US[ sval%100 ];              \
    buffer[1] = TEMP_US[ sval/100 ];              \
    buffer[0] = TEMP_US[ value/TEN_TO_THE_8th ];  \
    length = ( value < TEN_TO_THE_9th ? 9 : 10 ); \
  }                                               \
}

LOOKUP 

/* LOOKUP performs a binary search of valueTable[] and returns an index such that:
valueTable[index] <= value < valueTable[index+1]
valueTable[numSyms-1] and valueTable[numSyms] should both equal FFFFFFFF, so that index will be numSyms-1 
in this case. */

#define LOOKUP(value,index,valueTable,numSyms,temp) \
{                                   \
  register ulong _lo, _hi;          \
                                    \
  temp = (char *) valueTable;       \
  _lo = 0;                          \
  _hi = numSyms;                    \
  while ( _lo+1 != _hi )            \
  {                                 \
    index = (_lo + _hi) >> 1;       \
    if ( value < TEMP_UL[index] )   \
      _hi = index;                  \
    else                            \
      _lo = index;                  \
  }                                 \
  index = _lo;                      \
}

OUTPUT_SYMBOL

/* OUTPUT_SYMBOL writes "symbol+offset" into the output buffer.  outPtr is bumped past the string.  Remember 
that a symbol name is terminated with a '\r', not '\0'. */

#define OUTPUT_SYMBOL(offset,symName,outPtr,temp) \
{                                               \
  register ulong _offset;                       \
                                                \
  /* Copy symbol name */                                                                     \
  {                                             \
    temp = symName;                             \
    while ( ( *outPtr++ = *temp++ ) != '\r' ) ; \
  }                                             \
                                                \
/* We've copied the \r into the output buffer.  \ If offset is nonzero, replace \r with +  \ and output the offset 
(decimal).  If offset is zero, back up one char.  */                          \                   
                                                                                                             \
  _offset = offset;                             \
  if ( _offset )                                \
  {                                             \
    ushort _buffer[5], _bufLen;                 \
    ULTOA(_offset,_buffer,_bufLen,temp)         \
    {                                           \
      temp = ((char*) &_buffer[5]) - _bufLen;   \
      *(outPtr-1) = '+';                        \
      while ( _bufLen-- )                       \
        *outPtr++ = *temp++;                    \
    }                                           \
  }                                             \
  else outPtr--;  /* offset is zero */          \
}

OUTPUT_ADDRESS

/* OUTPUT_ADDRESS write "[symbol+offset  ]" into the output buffer.  outPtr is bumped past the string. 
 There will be exactly symLen characters between "[" and "]".  Truncate the symbol name or pad with spaces 
as necessary.  _count is the number of characters remaining.  _trunc is the number of characters remaining 
in the symbol name (possibly truncated).  It gets reused in the second for loop to hold the number of digits 
remaining in the decimal offset. */

#define OUTPUT_ADDRESS(offset,symName,symLen,outPtr,temp) \
{                                                   \
  register ulong _offset = offset;                  \
  if ( _offset )                                    \
  {                                                 \
    ushort _buffer[5], _bufLen;                     \
    ULTOA(_offset,_buffer,_bufLen,temp)             \
    {                                               \
      register int _count, _trunc;                  \
      *outPtr++ = '[';                              \
      for ( temp = symName, _count = symLen,        \
                _trunc = _count-_bufLen-1;          \
            _trunc && *temp != '\r';                \
            _count--, _trunc-- )                    \
        *outPtr++ = *temp++;                        \
                                                    \
      *outPtr++ = '+';                              \
      _count--;                                     \
      for ( temp = ((char*) &_buffer[5]) - _bufLen, \
                _trunc = _bufLen;                   \
            _trunc;                                 \
            _count--, _trunc-- )                    \
        *outPtr++ = *temp++;                        \
      while ( _count-- )                            \
        *outPtr++ = ' ';                            \
      *outPtr++ = ']';                              \
    }                                               \
  }                                                 \
  else                                              \
  {                                                 \
    register int _count;                            \
    *outPtr++ = '[';                                \
    for ( temp = symName, _count = symLen;          \
          _count && *temp != '\r';                  \
          _count-- )                                \
      *outPtr++ = *temp++;                          \
    while ( _count-- )                              \
      *outPtr++ = ' ';                              \
    *outPtr++ = ']';                                \
  }                                                 \
}


parseSymbols

/* parseSymbols() parses the symbol file.  Each element of name[] gets a pointer to a symbol name.  Each 
element of value[] gets the value of a symbol.  Note that each symbol name is terminated by '\r', not '\0'. 
 */

static unsigned short parseSymbols( char *buffer,
                                    char **name,
                                    ulong *value )
{
  register char *ptr;
  register char *temp;
  char **nextName;
  ulong *nextValue;
  ushort numSymbols;

  nextName = name;    /* where to save info for */
  nextValue = value;  /* the next symbol */
  numSymbols = 0;

  ptr = buffer;
  while ( *ptr )
  {
    /* The first 8 characters must be a hex number */
    XTOUL(ptr,*nextValue,temp)

    /* Skip whitespace between value and symbol */
    while ( *ptr++ == ' ' ) ;

    /* Save pointer to start of symbol */
    *nextName = ptr-1;

    /* Find start of next line */
    while ( *ptr++ != '\r' ) ;

    nextName++;
    nextValue++;
    numSymbols++;
  }

/ * Duplicate last symbol so the LOOKUP macro finds FFFFFFFF correctly.  */
  *nextValue = *(nextValue-1);

  return numSymbols;
}

convert

/* convert() converts 8 digit hex values in the input file.  It is also responsible for writing the output bufffer 
to the output file.  */

static void convert(
            char *inputBuffer, char *outputBuffer,
            char **symbolName, ulong *symbolValue,
            ushort numSymbols, ushort symLength,
            size_t inputLength, FILE *outputFile )
{
  register char *inPtr, *outPtr;
  register char *temp;
  ulong addrValue, nextValue, *nextValuePointer;
  char *addrName, **nextName, *endPtr, *writeThreshold;

  /* inPtr and outPtr are both register variables.  The third address register variable is temp.   */

  inPtr = inputBuffer;
  outPtr = outputBuffer;

  /* Stop when inPtr equals endPtr.  Flush the output buffer to disk when outPtr exceeds writeThreshold. 
  */

  endPtr = inPtr + inputLength;
  writeThreshold = outputBuffer + OUTPUT_THRESHOLD;

  /* Add eight ASCII '0's to end of input file.  The search algorithm expects eight hex digits after each \r, even 
at the end of the file.   */

  {
    temp = endPtr;
    *temp++ = '0'; *temp++ = '0';
    *temp++ = '0'; *temp++ = '0';
    *temp++ = '0'; *temp++ = '0';
    *temp++ = '0'; *temp++ = '0';
  }

  /* Force lookup first time through.  */
  addrValue = 0xFFFFFFFF;
  nextValue = 0;    /* in case first address is FFFFFFFF */
  nextValuePointer = symbolValue-1;

  /* Loop once per input line */
  while ( inPtr != endPtr )
  {

    /* Assume that the first eight characters of each line are all hex digits.  Convert this value to [symbol+offset] 
form.  A line will usually have the same symbol as the previous line, or sometimes the next higher symbol. 
 Thus, we check for these two cases first and do a binary search only as a last resort.     */

    {
      register ulong address;
      XTOUL(inPtr,address,temp)
      if ( address < addrValue )
        goto lookup;  /* address going backward (unusual) */
      else if ( address >= nextValue )
      {
        /* Address doesn't match current symbol.  */
        /* Check if it matches the next symbol.  */
        addrValue = nextValue;
        nextValue = *(++nextValuePointer);
        if ( address < nextValue )
          addrName = *nextName++; /* yes, it matches next */
        else
        {
          /* Doesn’t match current or next symbol, so do a full binary search */
          register ulong index;
        lookup:
          LOOKUP(address,index,symbolValue,numSymbols,temp)
          addrName = symbolName[index];
          nextName = symbolName + index + 1;
          nextValuePointer = symbolValue + index + 1;
          nextValue = *nextValuePointer;
          addrValue = *(nextValuePointer - 1);
        }
      }
      OUTPUT_ADDRESS(address-addrValue,addrName,
                     symLength,outPtr,temp)
    }

/* Scan the rest of the line for 8 digit hex numbers.  It is often possible to jump ahead many characters when 
we find a non-hex digit.  We check seven characters ahead for a hex digit, then six characters ahead, etc. 
 If we find a non-hex digit we know the intervening characters can't possibly be an 8 digit number.  It turns 
out that if there is a \r anywhere in the next eight characters, it will be the first non-hex character we encounter. 
 This happens because the first eight characters of a line are hex digits, and we are looking ahead at most 
eight characters.  Thus, if we start beyond a \r, we will see hex digits all the way back to the \r.  There can't 
be a second \r hiding earlier in the line since each line has at least eight characters; another whole line wouldn't 
fit into the remaining characters.  When we jump to copy8..copy1, we only need to check for \r at copy1. 
    */

    /* Loop until end of line */
    while ( *inPtr != '\r' )
    {
      {
        temp = inPtr+7;
        if ( !ishex[ *temp-- ] ) goto copy8;
        if ( !ishex[ *temp-- ] ) goto copy7;
        if ( !ishex[ *temp-- ] ) goto copy6;
        if ( !ishex[ *temp-- ] ) goto copy5;
        if ( !ishex[ *temp-- ] ) goto copy4;
        if ( !ishex[ *temp-- ] ) goto copy3;
        if ( !ishex[ *temp-- ] ) goto copy2;
        if ( !ishex[ *temp ] ) goto copy1;
      }

      {
        /* Found 8 hex digits.  Convert to binary and ouput in "symbol+offset" form.    */

        register ulong value, index;
        XTOUL(inPtr,value,temp)
        LOOKUP(value,index,symbolValue,numSymbols,temp)
        OUTPUT_SYMBOL(value-symbolValue[index],
                      symbolName[index],outPtr,temp)
        continue;
      }

      /* Didn't have 8 hex digits.  Copy to output and check for \r.  */

      copy8:  *outPtr++ = *inPtr++;
      copy7:  *outPtr++ = *inPtr++;
      copy6:  *outPtr++ = *inPtr++;
      copy5:  *outPtr++ = *inPtr++;
      copy4:  *outPtr++ = *inPtr++;
      copy3:  *outPtr++ = *inPtr++;
      copy2:  *outPtr++ = *inPtr++;
      copy1:  if ( *inPtr != '\r' )
                *outPtr++ = *inPtr++;
              else break; /* exit the inner while loop */
    }

    /* Now we're at the end of the line.  Copy the \r, */
    /* then flush the output buffer if we've run past the threshold.  */

    *outPtr++ = '\r';
    inPtr++;

    if ( outPtr >= writeThreshold )
    {
      fwrite(outputBuffer,1,outPtr-outputBuffer,outputFile);
      outPtr = outputBuffer;
    }
  }

  /* We have reached the end of the input file.  */
  /* Flush the rest of the output buffer.       */

  if ( outPtr != outputBuffer )
    fwrite(outputBuffer,1,outPtr-outputBuffer,outputFile);
}

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Macs Fan Control 1.5.14 - Monitor and co...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more
VueScan 9.7.96 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
FileMaker Pro 19.6.1 - Quickly build cus...
FileMaker Pro is the tool you use to create a custom app. You also use FileMaker Pro to access your app on a computer. Start by importing data from a spreadsheet or using a built-in Starter app to... Read more
Duet 3.1.0.0 - Use your iPad as an exter...
Duet is the first app that allows you to use your iDevice as an extra display for your Mac using the Lightning or 30-pin cable. Note: This app requires a iOS companion app. Release notes were... Read more
Firefox 107.0.1 - Fast, safe Web browser...
Firefox offers a fast, safe Web browsing experience. Browse quickly, securely, and effortlessly. With its industry-leading features, Firefox is the choice of Web development professionals and casual... Read more
War Thunder 2.21.1.91 - Multiplayer war...
In War Thunder, aircraft, attack helicopters, ground forces and naval ships collaborate in realistic competitive battles. You can choose from over 1,500 vehicles and an extensive variety of combat... Read more
Numbers 12.2.1 - Apple's spreadshee...
With Apple Numbers, sophisticated spreadsheets are just the start. The whole sheet is your canvas. Just add dramatic interactive charts, tables, and images that paint a revealing picture of your data... Read more
DEVONthink Pro 3.8.7 - Knowledge base, i...
DEVONthink is DEVONtechnologies' document and information management solution. It supports a large variety of file formats and stores them in a database enhanced by artificial intelligence (AI). Many... Read more
Drive Genius 6.2.3 - $79.00
Drive Genius features a comprehensive Malware Scan. Automate your malware protection. Protect your investment from any threat. The Malware Scan is part of the automated DrivePulse utility. DrivePulse... Read more
VLC Media Player 3.0.18 - Popular multim...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more

Latest Forum Discussions

See All

‘Genshin Impact’ Version 3.3 Pre-Install...
Following the reveal of the release date and more for Genshin Impact (Free) version 3.3 ‘All Senses Clear, All Existence Void’, HoYoverse showcased the Genius Invokation TCG that arrives this week in the update. | Read more »
TouchArcade Game of the Week: ‘Sling Min...
The world of PC games has always blown my mind because there’s just SO MUCH stuff out there that it’s not uncommon at all for there to be a game that’s well-liked and well-reviewed, and seemingly quite popular with a solid fanbase, and have it be... | Read more »
SwitchArcade Round-Up: Reviews Featuring...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 2nd, 2022. So, today turned out a little quieter than the usual Friday. It was so quiet, in fact, that I decided to pen a few reviews. The Knight Witch, Railbound, and Donut... | Read more »
Blue Archive reveals its latest event st...
Nexon has announced the new update for Blue Archive, under the name of An Unconcealed Heart. Featuring a battle between two academies, the story will follow a group struggling to gain recognition, and will bring three new students to recruit. [... | Read more »
Dead Cells+ Is Out Now on Apple Arcade a...
Following the major update for Dead Cells on iOS and Android a few days ago, Playdigious has brought Dead Cells+ () to Apple Arcade. As an App Store Great, Dead Cells+ includes all prior paid DLC and content updates. It also has exclusive mobile... | Read more »
SwitchArcade Round-Up: ‘Romancing SaGa’,...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 1st, 2022. Wow, December. We’re already at the last month of the year? Phew. I have a lot of work to finish in the next few weeks. As for today, we’ve got a little news, a... | Read more »
‘Railbound’ Update Now Available Adding...
One of our favorite puzzlers released this year is Railbound from Afterburn Games, which hit in early September and earned our Game of the Week recognition for being an absolutely ace logic puzzler. The goal is to place rail pieces down in order to... | Read more »
The Seven Deadly Sins: Grand Cross celeb...
Netmarble Corporation has pulled out all the stops to celebrate the 3 and a half year anniversary of The Seven Deadly Sins: Grand Cross. The Grand Cross 3.5th Year Anniversary the Ultimate One, a rather wordy title, brings with it a brand new... | Read more »
‘Skullgirls Mobile’ Major Update 5.2 Out...
Developer Hidden Variable pushed out a major update for Skullgirls Mobile (Free) a few hours ago. The version 5.2 update brings in Black Dahlia (before the console and PC game), Retakes, XP Treats, free gifts, and more. Since launch, Skullgirls... | Read more »
Out Now: ‘Disgaea 4’, ‘Romancing SaGa: M...
Each and every day new mobile games are hitting the App Store, and so each week we put together a big old list of all the best new releases of the past seven days. Back in the day the App Store would showcase the same games for a week, and then... | Read more »

Price Scanner via MacPrices.net

Holiday Sale: Apple AirPods Pro for only $199...
Amazon has new 2022 AirPods Pro in stock and on sale for $199.99 shipped as part of their Holiday sale. Their price is $50 off Apple’s MSRP, equaling their Black Friday price, and it’s the lowest... Read more
New Holiday Sale: Apple retailers are offerin...
Several Apple retailers lowered prices on 10.9″ iPad Airs overnight to lows of $100 off MSRP starting at $499. Their prices are the lowest available for iPad Airs anywhere this Holiday season right... Read more
New Holiday sale at Amazon: Take $50 off Appl...
Amazon has Apple’s new 10th-generation iPads in stock and on sale, for the first time, for $50 off MSRP starting at only $399. Their discount applies to all models and all colors. With the discount,... Read more
Holiday Sale: Get an 8.3″ Apple iPad mini for...
Sams Club has 10.9″ 64GB iPad minis on Holiday sale for $80-$100 off MSRP through December 7, 2022. With their discount, prices start at $399 — the cheapest price for a new iPad mini from any of the... Read more
Sams Club Holiday December Event sale: Apple...
Apple AirPods Max headphones are on sale at Sams Club for $110 off MSRP ($439) as part of their December Event sale, ending on December 7, 2022, valid for all colors. Sale price for online orders... Read more
Apple’s 10.2″ 64GB 9th-generation iPads are o...
Sams Club has 9th-generation 64GB iPads on Holiday sale for $60 off MSRP through December 7, 2022. With their discount, prices start at $259 — the cheapest price for a new iPad from any of the Apple... Read more
11″ 128GB WiFi M2 iPad Pro on sale for $749,...
B&H Photo has the new 11″ 128GB WiFi M2-powered iPad Pro (in Space Gray or Silver) on Holiday sale for $749 including free 1-2 day shipping to most US addresses. Their price is $50 off MSRP and... Read more
Find the best Holiday sale price on an iPad u...
We’ve updated our iPad Price Trackers with the latest information on the new 10th-generation iPads, M2-powered iPad Pros, M1 iPad Airs, iPad minis, and 9th generation iPads from Apple’s authorized... Read more
Apple retailers are offering $100-$150 Holida...
Apple retailers have posted their most-recent Holiday sale prices on 13″ MacBook Airs. Take up to $150 off MSRP on M2-powered Airs with these sales with prices starting at only $1099. Free shipping... Read more
Holiday Sale: Apple’s 14″ MacBook Pros with M...
B&H Photo is offering $200-$300 discounts on Apple’s 14″ MacBook Pros with M1 Pro CPUs as part of their Holiday 2022 sale, with prices starting at $1799. Free 1-2 day shipping is available to... Read more

Jobs Board

Support Technician II - *Apple* Support - O...
…problems and acting as a liaison between customers and resolving groups. As an Apple Technical Specialist, you will be supporting many of our popular Apple Read more
*Apple* Electronic Repair Technician - PlanI...
…a highly motivated individual to join our Production Department as an Apple Electronic Repair Technician. The computer repair technician will diagnose, assemble, Read more
Lead Developer - *Apple* tvOS - Rumble (Uni...
…earnings, and positive sentiment About the role: We are looking for a Lead Apple tvOS Developer to join our application engineering team to expand our video centric Read more
Tier 1 Endpoint Engineer - *Apple* - Red Ri...
…Desk on site, at our Client's location, with a focus on support to Apple products. This position will handle technical support requests directly from customers and Read more
Product Manager II - *Apple* - DISH (United...
…you will be doing We seek an ambitious, data-driven thinker to assist the Apple Product Development team as our new Retail Wireless division continues to grow and Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.