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
$99.88
Apple Inc.
-0.87
MSFT
$46.20
Microsoft Corpora
-0.16
GOOG
$572.65
Google Inc.
-4.71

MacTech Search:
Community Search:

Software Updates via MacUpdate

Cocktail 8.0 Beta 2 - General maintenanc...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
QuickBooks 2015 16.0.0.1352 R1 - Financi...
QuickBooks 2015 helps you manage your business easily and efficiently. Organize your finances all in one place, track money going in and out of your business, and spot areas where you can save.... Read more
Mac DVDRipper Pro 5.0.1 - Copy, backup,...
Mac DVDRipper Pro is the DVD backup solution that lets you protect your DVDs from scratches, save your batteries by reading your movies from your hard disk, manage your collection with just a few... Read more
Apple OS X bash Update 1.0 - Fix for sec...
The OS X bash Update fixes a security flaw in the bash UNIX shell on OS X 10.9.5 (also on OS X 10.8 and 10.7 [see Related Links below]). OS X 10.9.5 or later Downloads for OS X 10.8 and OS X 10.7 in... Read more
SyncTwoFolders 2.0.5 - Syncs two user-sp...
SyncTwoFolders simply synchronizes two folders. It supports synchronization across mounted network drives and it is a possibility to run a simulation showing in a log what will be done. Please visit... Read more
FinderPop 2.5.7 - Classic Mac utility, n...
FinderPop is a Universal preference pane that extends OS X's contextual menus using a FinderPop Items folder much as the Apple Menu Items folder used to do for the Apple menu. It has other features... Read more
VueScan 9.4.45 - 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
LibreOffice 4.3.2.2 - Free Open Source o...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
calibre 2.4 - Complete e-library managem...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital... Read more
Default Folder X 4.6.9b1 - Enhances Open...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click... Read more

Latest Forum Discussions

See All

The Sagas of Fire*Wolf (Games)
The Sagas of Fire*Wolf 1.0 Device: iOS Universal Category: Games Price: $9.99, Version: 1.0 (iTunes) Description: | Read more »
BuggyFun Review
BuggyFun Review By Amy Solomon on October 1st, 2014 Our Rating: iPad Only App - Designed for the iPad BuggyFun allows children to create their own tracks for bugs to interact with for a unique open-ended experience.   | Read more »
Fold the Adventure Review
Fold the Adventure Review By Jennifer Allen on October 1st, 2014 Our Rating: :: AWKWARD FOLDSUniversal App - Designed for iPhone and iPad Fold pieces of paper to create platforms for a princely rabbit in this puzzle game; something... | Read more »
WW2: Sandbox. Strategy & Tactics (G...
WW2: Sandbox. Strategy & Tactics 1.0.0 Device: iOS Universal Category: Games Price: $9.99, Version: 1.0.0 (iTunes) Description: Sandbox is the unlimited sequel to our Strategy & Tactics: World War II. We've abandoned... | Read more »
apeFilter (Music)
apeFilter 1.0 Device: iOS Universal Category: Music Price: $6.99, Version: 1.0 (iTunes) Description: | Read more »
Shred It! Review
Shred It! Review By Jennifer Allen on September 30th, 2014 Our Rating: :: GORGEOUS BUT BASICUniversal App - Designed for iPhone and iPad It might look lovely, but Shred It! is a pretty shallow endless runner/snowboarding game.   | Read more »
Check Out the New Teaser Trailer forGAME...
Check Out the New Teaser Trailer forGAMEVIL’s Darkness Reborn Posted by Jessica Fisher on September 30th, 2014 [ permalink ] Darkness Reborn, by GAMEVIL< | Read more »
It Came From Canada: Angry Birds: Transf...
Anyone afraid that throwing Transformers into the Angry Birds mix would result in a Michael Bay-level of childhood pillaging can rest easy. While Rovio’s famous fowls may be a 21st century staple, Angry Birds: Transformers wears its affection for... | Read more »
Anomaly Defenders Review
Anomaly Defenders Review By Jennifer Allen on September 30th, 2014 Our Rating: :: STRONG DEFENSESUniversal App - Designed for iPhone and iPad Wrapping up the successful Tower Defense series, Anomaly Defenders is a blast.   | Read more »
Double the Dragons, Double the Fun – The...
Double the Dragons, Double the Fun – The Majesty Bundle is Now Available on the App Store Posted by Jessica Fisher on September 30th, 2014 [ permalink ] Majesty, by | Read more »

Price Scanner via MacPrices.net

Roundup of Apple Mac and iPad Education disco...
Purchase a new Mac or iPad 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,... Read more
Apple Boycotts German Magazine Computer Bild...
Apple has revoked its PR accreditation of Germany’s Computer Bild, Europe’s best-selling PC magazine, in reaction to Bild’s posting of a “#Bentgate” YouTube video. Axel Telzerow, editor in chief of... Read more
iPhone 6 & iPhone 6 Plus Available in Chi...
Apple has announced that iPhone 6 and iPhone 6 Plus will be available in China beginning Friday, October 17 from the Apple Online Store (http://www.apple.com), Apple’s retail stores, and an expansive... Read more
MacBook Airs on sale for $100 off MSRP, start...
Best Buy has the new 2014 MacBook Airs on sale for $100 off MSRP on their online store. Choose free home shipping or free local store pickup (if available). Prices valid for online orders only, in-... Read more
Apple Releases OS X Mavericks bash Update 1.0...
Apple has released a patch update for OS X Mavericks users to address the recently-detected “Shellshock” security bug in BSD UNIX’s bash shell. Apple says only a few Mac users who had manually... Read more
Pivotal Payments Ready for Apple Pay – FlexPo...
Pivotal Payments, a provider of merchant services and global payment processing solutions, has announced its proprietary FlexPoint platform will support credit and debit transactions through Apple’s... Read more
iStabilizer Announces Tabarm — First Friction...
iStabilizer, a specialist in universal lightweight compact tripods, steady cams, dollies, mounts, and remotes for smartphones, tablets, and cameras, announced today the iStabilizer tabArm, the first... Read more
IStabilizer Flex Smartphone Tripod Wins Usa T...
iStabilizer, a specialist in universal lightweight compact tripods, steady cams, and other products for smartphones, tablets, and cameras, has announced today that its iStabilizer Flex smartphone... Read more
13-inch 2.8GHz Retina MacBook Pro on sale for...
B&H Photo has the new 2014 13″ 2.8GHz Retina MacBook Pro on sale for $1699.99 including free shipping plus NY sales tax only. They’ll also include free copies of Parallels Desktop and LoJack for... Read more
15-inch Retina MacBook Pros on sale for up to...
B&H Photo has the new 2014 15″ Retina MacBook Pros on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only. They’ll also include free copies of Parallels Desktop... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
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 (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
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.