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);
}

 
AAPL
$519.01
Apple Inc.
+1.05
MSFT
$40.40
Microsoft Corpora
+0.65
GOOG
$556.54
Google Inc.
+20.10

MacTech Search:
Community Search:

Software Updates via MacUpdate

PDFpenPro 6.2 - Advanced PDF toolkit for...
PDFpenPro allows users to edit PDF's easily. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Create... Read more
PDFpen 6.2 - Edit and annotate PDFs with...
PDFpen allows users to easily edit PDF's. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Features... Read more
Monolingual 1.5.9 - Remove unwanted OS X...
Monolingual is a program for removing unnecesary language resources from OS X, in order to reclaim several hundred megabytes of disk space. It requires a 64-bit capable Intel-based Mac and at least... Read more
Maya 2015 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
Starcraft II: Wings of Liberty 1.1.1.180...
Download the patch by launching the Starcraft II game and downloading it through the Battle.net connection within the app. Starcraft II: Wings of Liberty is a strategy game played in real-time. You... Read more
Sibelius 7.5.0 - Music notation solution...
Sibelius is the world's best-selling music notation software for Mac. It is as intuitive to use as a pen, yet so powerful that it does most things in less than the blink of an eye. The demo includes... Read more
Typinator 5.9 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more
MYStuff Pro 2.0.16 - Create inventories...
MYStuff Pro is the most flexible way to create detail-rich inventories for your home or small business. Add items to MYStuff by dragging and dropping existing information, uploading new images, or... Read more
TurboTax 2013.r17.002 - Manage your 2013...
TurboTax guides you through your tax return step by step, does all the calculations, and checks your return for errors and overlooked deductions. It lets you file your return electronically to get... Read more
TrailRunner 3.8.769 - Route planning for...
Note: While the software is classified as freeware, it is actually donationware. Please consider making a donation to help support development. TrailRunner is the perfect companion for runners,... Read more

Latest Forum Discussions

See All

Fourcast Review
Fourcast Review By Jennifer Allen on April 16th, 2014 Our Rating: :: VIDEO POTENTIALiPhone App - Designed for the iPhone, compatible with the iPad Fourcast is a great idea for combining video clips, but it does lack a number of... | Read more »
Hearthstone: Heroes of Warcraft is Avail...
Hearthstone: Heroes of Warcraft is Available on the U.S. App Store Right Now – Gogogogo! Posted by Rob Rich on April 16th, 2014 [ permalink ] | Read more »
Grammar Pop HD Review
Grammar Pop HD Review By Jennifer Allen on April 16th, 2014 Our Rating: :: FUN LEARNINGiPad Only App - Designed for the iPad Learning the different parts of speech isn’t always fun, but Grammar Pop HD makes it much more... | Read more »
Groundskeeper2 Review
Groundskeeper2 Review By Nadia Oxford on April 16th, 2014 Our Rating: :: SLICE THOSE ALIEN SLIMEUniversal App - Designed for iPhone and iPad Putting aside some minor control issues, Groundskeeper2 is a fun and furious action/... | Read more »
Pinnacle Studio for iPhone (Photography...
Pinnacle Studio for iPhone 5.0 Device: iOS iPhone Category: Photography Price: $9.99, Version: 5.0 (iTunes) Description: | Read more »
Season 3 of Zombies, Run! Starts Right N...
Season 3 of Zombies, Run! | Read more »
Snupps Review
Snupps Review By Jennifer Allen on April 16th, 2014 Our Rating: :: USEFUL LISTINGUniversal App - Designed for iPhone and iPad Got a huge collection that you need to organize, or just want to share with others? Snupps has it covered... | Read more »
Toad Rider Goes Free for a Limited Time,...
Toad Rider Goes Free for a Limited Time, Starting This Week Posted by Tre Lawrence on April 16th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Knights of Pen & Paper is Free for a...
Knights of Pen & Paper is Free for a Limited Time – Don’t Wait for a Natural 20, Get it Now! Posted by Rob Rich on April 16th, 2014 [ permalink ] | Read more »
R.B.I. Baseball 14 Review
R.B.I. Baseball 14 Review By Blake Grundman on April 16th, 2014 Our Rating: :: RETRO REVIVEDUniversal App - Designed for iPhone and iPad What was old is new again, as the MLB attempts to taking baseball gaming back to its retro... | Read more »

Price Scanner via MacPrices.net

Microsoft Blinks – Drops Microsoft Office 365...
Microsoft has dropped the annual subscription fee for Microsoft Office 365 Personal – which is needed in order to create and edit documents in Microsoft Office for iPad. However, Apple’s iOS and OS X... Read more
New AVG Vault Apps for iOS and Android Help K...
AVG Technologies N.V. an online security company for 177 million active users, has announced the launch of its latest mobile application, AVG Vault. The free app introduces an innovative user... Read more
Free Local Carrot iPhone App Helps Find Fresh...
I love fresh vegetables. I’m not a vegan, although I was for several years in the 1980s, but fresh vegetables and other whole foods are still my dietary mainstays as a matter of taste rather than... Read more
Apple refurbished iPad Airs available startin...
Apple is now offering Certified Refurbished iPad Airs for up to $140 off MSRP. Apple’s one-year warranty is included with each model, and shipping is free. The following Airs are available today: -... Read more
21-inch 2.7GHz iMac on sale for $1179, save $...
B&H Photo has the 21″ 2.7GHz iMac on sale for $1179 including free shipping plus NY sales tax only. Their price is $120 off MSRP. Add an iMac to your shopping cart, and B&H will offer an... Read more
Download our app, iTracx, for iOS and Android
MacPrices is proud to offer readers a free iOS app (iPhones, iPads, & iPod touch) and Android app (Google Play and Amazon App Store) called iTracx, which allows you to glance at today’s lowest... Read more
Education discounts shave up to $300 off the...
Purchase a new Mac at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free, and all... Read more
Save $50 on Mac mini Server
B&H Photo has the 2012 Mac mini Server on sale for $949 including free shipping plus NY sales tax only. Their price is $50 off MSRP. Read more
PhatWare’s “Ultimate Writing App For iOS” Ren...
PhatWare Corp. has announced it has renamed its new WritePro word processing app for iPhone and iPad: WritePad Pro. The decision to change the app’s name to leverages the strong brand awareness and... Read more
Full Resolution Photo Editor Tint Mint 1.0 Re...
California based independent developer, Jeffrey Sun, creator of the iOS app Modern Editor, has released Tint Mint, a new photography app for editing enthusiasts. The app costs a dollar, and it packs... Read more

Jobs Board

*Apple* Retail - Manager - Holyoke - Apple I...
Job Summary Keeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you’re a master of them all. In the store’s fast-paced, Read more
*Apple* Retail - Manager - Apple (United Sta...
Job SummaryKeeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you're a master of them all. In the store's fast-paced, dynamic Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Retail - Market Leader - Cincinnati...
…challenges of developing individuals, building teams, and affecting growth across Apple Stores. You demonstrate successful leadership ability - focusing on excellence Read more
*Apple* Retail - Manager - SoHo - Apple (Uni...
Job SummaryKeeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you're a master of them all. In the store's fast-paced, dynamic Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.