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
$100.57
Apple Inc.
+0.04
MSFT
$44.95
Microsoft Corpora
-0.38
GOOG
$584.49
Google Inc.
-2.37

MacTech Search:
Community Search:

Software Updates via MacUpdate

Tidy Up 3.0.15.0 - Find duplicate files...
Tidy Up is a complete duplicate finder and disk-tidiness utility. With Tidy Up you can search for duplicate files and packages by the owner application, content, type, creator, extension, time... Read more
Parallels Desktop 10.0 - Run Windows app...
Parallels Desktop is simply the world's bestselling, top-rated, and most trusted solution for running Windows applications on your Mac. With Parallels Desktop for Mac, you can seamlessly run both... Read more
Apple Final Cut Pro X 10.1.3 - Professio...
Apple Final Cut Pro X is a professional video editing solution.Completely redesigned from the ground up, Final Cut Pro adds extraordinary speed, quality, and flexibility to every part of the post-... Read more
Apple Compressor 4.1.3 - Adds power and...
Compressor adds power and flexibility to Final Cut Pro X export. Customize output settings, work faster with distributed encoding, and tap into a comprehensive set of delivery features. Powerful... Read more
Chromium 36.0.1985.143 - Fast and stable...
Chromium is an open-source browser project that aims to build a safer, faster, and more stable way for all Internet users to experience the web. FreeSMUG-Free OpenSource Mac User Group build is... Read more
Macgo Blu-ray Player 2.10.6.1691 - Blu-r...
Macgo Mac Blu-ray Player can bring you the most unforgettable Blu-ray experience on your Mac. Overview Macgo Mac Blu-ray Player can satisfy just about every need you could possibly have in a Blu-ray... Read more
Apple Motion 5.1.2 - Create and customiz...
Apple Motion is designed for video editors, Motion 5 lets you customize Final Cut Pro titles, transitions, and effects. Or create your own dazzling animations in 2D or 3D space, with real-time... Read more
A Better Finder Rename 9.39 - File, phot...
A Better Finder Rename is the most complete renaming solution available on the market today. That's why, since 1996, tens of thousands of hobbyists, professionals and businesses depend on A Better... Read more
PopChar X 6.6 - Floating window shows av...
PopChar X helps you get the most out of your font collection. With its crystal-clear interface, PopChar X provides a frustration-free way to access any font's special characters. Expanded... Read more
MacUpdate Desktop 6.0.2 - Install Mac ap...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more

Latest Forum Discussions

See All

Cubic Castles Review
Cubic Castles Review By Rob Thomas on August 20th, 2014 Our Rating: :: CASTLE CRAFTINGiPad Only App - Designed for the iPad Some ridiculously frustrating camera issues aside, Cubic Castles is a pretty neat, voxel-based crafting... | Read more »
Space Colors – Tips, Tricks, Strategies,...
Hello Cadets: Want to know what we thought about this hectic space combat/roguelike? Check out our Space Colors review! Space Colors is a cool shooter/roguelike from Team Chaos. You travel from planet to planet across a huge galaxy and complete a... | Read more »
Tap Sports Baseball – Tips, Tricks, and...
Tap Sports Baseball is a pretty simple game to learn, but that doesn’t mean it’s an easy game to master, by any means. To start your batting career off well, we thought we’d give you the heads up on some handy tips and tricks. Hey Batter-Batter:... | Read more »
Tap Sports Baseball Review
Tap Sports Baseball Review By Jennifer Allen on August 20th, 2014 Our Rating: :: LET'S PLAY BALLUniversal App - Designed for iPhone and iPad Tap Sports Baseball is briefly fun but lacks some important features.   | Read more »
Earn to Die 2 Set to Drive in to the App...
Earn to Die 2 Set to Drive in to the App Store Later This Year Posted by Ellis Spice on August 20th, 2014 [ permalink ] Not Doppler has announced that Earn to Die 2, a sequel to their successful game | Read more »
Frontier Heroes Review
Frontier Heroes Review By Andrew Fisher on August 20th, 2014 Our Rating: :: BLAZES NO TRAILSUniversal App - Designed for iPhone and iPad Despite awesome visuals and great music, Frontier Heroes just doesn’t quite deliver enough fun... | Read more »
Echo Prime is Now on Sale for $0.99
Echo Prime is Now on Sale for $0.99 Posted by Jessica Fisher on August 20th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Star Realms Review
Star Realms Review By Andrew Fisher on August 20th, 2014 Our Rating: :: A STAR IS BORNUniversal App - Designed for iPhone and iPad Star Realms is an excellent adaptation of an outstanding deck-builder. With great visuals and an... | Read more »
This. Is. SPRINGFIELD! War comes to The...
This. Is. SPRINGFIELD! | Read more »
One Tap RPG Review
One Tap RPG Review By Campbell Bird on August 20th, 2014 Our Rating: :: DUNGEON SLIDERUniversal App - Designed for iPhone and iPad This casual arcade game introduces some very light rpg elements into its fantasy-themed pachinko... | Read more »

Price Scanner via MacPrices.net

Apple now offering certified refurbished 2014...
 The Apple Store is now offering Apple Certified Refurbished 2014 MacBook Airs for up to $180 off the cost of new models. An Apple one-year warranty is included with each MacBook, and shipping is... Read more
Best Buy’s College Student Deals: $100 off Ma...
Take an additional $100 off all MacBooks and iMacs, $50 off iPad Airs and iPad minis, at Best Buy Online with their College Students Deals Savings, valid through September 6th. Anyone with a valid .... Read more
MacBook Airs on sale for $100 off MSRP, free...
B&H Photo has three 2014 MacBook Airs on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only. They also include free copies of Parallels Desktop and LoJack for Laptops... Read more
Razer Taipan Mouse For Gamers And Non-Gamers...
If you’re a serious gamer on either Mac or Windows PCs, a serious gaming mouse is a necessity for first-tier performance. However, even if like me you’re not much of a gamer, there’s still a strong... Read more
15-inch 2.2GHz MacBook Pro on sale for $1899,...
Adorama has the new 15″ 2.2GHz Retina MacBook Pro on sale for $1899 including free shipping plus NY & NJ sales tax only. Their price is $100 off MSRP, and it’s the lowest price available for this... Read more
Mid-Size Tablet Shootout Posted: iPad mini wi...
I ‘m curious about how many iPads Apple is actually selling these days. It’s been widely rumored and anticipated that new models with A8 SoCs, 2 GB of RAM, 8 megapixel cameras, and fingerprint... Read more
The 15 Biggest iPad Air Problems And How To A...
What’s this? Fifteen “biggest” problems with the iPad Air? Does that mean there are a lot of smaller problems as well? Say it isn’t so! My old iPad 2 has manifested no hardware problems in three... Read more
TYLT Syncable-Duo, 2-in-1 USB Cable With Appl...
TYLT has introduced the Syncable-Duo, a universal cable solution for charging and syncing data to smartphones and tablets. The Syncable-Duo eliminates the need for multiple cables by incorporating... Read more
Save up to $140 off MSRP with Apple refurbish...
Apple is 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. Stock tends to come and go with some of these... Read more
2.5GHz Mac mini on sale for $549, save $50
B&H Photo has the 2.5GHz Mac mini on sale for $549.99 including free shipping. That’s $50 off MSRP, and B&H will also include a free copy of Parallels Desktop software. NY sales tax only. Read more

Jobs Board

Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Solutions Consultant - Apple (United...
**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
Position Opening at *Apple* - Apple (United...
**Job Summary** Being a Business Manager at an Apple Store means you're the catalyst for businesses to discover and leverage the power, ease, and flexibility of Apple Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** At the Apple Store, you connect business professionals and entrepreneurs with the tools they need in order to put Apple solutions to work in their Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.