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
$101.06
Apple Inc.
+0.10
MSFT
$47.06
Microsoft Corpora
-0.46
GOOG
$587.37
Google Inc.
-8.71

MacTech Search:
Community Search:

Software Updates via MacUpdate

Monosnap 2.2.2 - Versatile screenshot ut...
Monosnap allows you to save screenshots easily, conveniently, and quickly, sharing them with friends and colleagues at once. It's the ideal choice for anyone who is looking for a smart and fast... Read more
Tunnelblick 3.4beta36 - GUI for OpenVPN...
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more
SoftRAID 5.0.4 - High-quality RAID manag...
SoftRAID allows you to create and manage disk arrays to increase performance and reliability. SoftRAID's intuitive interface and powerful feature set makes this utility a must have for any Mac OS X... Read more
Audio Hijack Pro 2.11.3 - Record and enh...
Audio Hijack Pro drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio with Audio Hijack... Read more
Airfoil 4.8.9 - Send audio from any app...
Airfoil allows you to send any audio to AirPort Express units, Apple TVs, and even other Macs and PCs, all in sync! It's your audio - everywhere. With Airfoil you can take audio from any... Read more
WhatRoute 1.13.0 - Geographically trace...
WhatRoute is designed to find the names of all the routers an IP packet passes through on its way from your Mac to a destination host. It also measures the round-trip time from your Mac to the... Read more
Chromium 37.0.2062.122 - 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
Attachment Tamer 3.1.14b9 - Take control...
Attachment Tamer gives you control over attachment handling in Apple Mail. It fixes the most annoying Apple Mail flaws, ensures compatibility with other email software, and allows you to set up how... Read more
Duplicate Annihilator 5.0 - Find and del...
Duplicate Annihilator takes on the time-consuming task of comparing the images in your iPhoto library using effective algorithms to make sure that no duplicate escapes. Duplicate Annihilator detects... Read more
jAlbum Pro 12.2 - Organize your digital...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code!... Read more

Latest Forum Discussions

See All

This Week at 148Apps: September 15-19, 2...
Expert App Reviewers   So little time and so very many apps. What’s a poor iPhone/iPad lover to do? Fortunately, 148Apps is here to give you the rundown on the latest and greatest releases. And we even have a tremendous back catalog of reviews; just... | Read more »
Kitty Powers’ Matchmaker – Tips, Tricks,...
Hey There, Kittens: | Read more »
Goblin Sword Review
Goblin Sword Review By Andrew Fisher on September 22nd, 2014 Our Rating: :: RETRO GOODNESSUniversal App - Designed for iPhone and iPad Fun visuals, good music, engaging level design, and lots of content make Goblin Sword an... | Read more »
Major New Update for CSR Racing Adds Fer...
Major New Update for CSR Racing Adds Ferrari and Multiplaye​r Posted by Jessica Fisher on September 22nd, 2014 [ permalink ] | Read more »
Veditor Review
Veditor Review By Jennifer Allen on September 22nd, 2014 Our Rating: :: PIMP YOUR VIDEOUniversal App - Designed for iPhone and iPad Want to add stickers and music to your videos? Veditor can do that easily.   | Read more »
1849′s Nevada Silver DLC is Still Search...
A few months ago, I took a look at 1849 from SomaSim. This Gold Rush-themed city builder for iPad had a fair bit going for it, but lacked in a few crucial areas to make it a true stand-out on the App Store. SomaSim has since added in a sandbox mode... | Read more »
Fruit Ninja Will be Reborn With a Massiv...
Fruit Ninja Will be Reborn With a Massive Update and Origins Animation Series Posted by Jessica Fisher on September 22nd, 2014 [ permalink ] Halfbrick Studios is rebuilding | Read more »
Daniel Tiger’s Grr-ific Feelings Review
Daniel Tiger’s Grr-ific Feelings Review By Amy Solomon on September 22nd, 2014 Our Rating: iPad Only App - Designed for the iPad Daniel Tiger’s Grr-ific Feelings includes activities that allow young children explore different... | Read more »
CloudMagic Updated for iOS 8 – Adds Inte...
CloudMagic Updated for iOS 8 – Adds Interactive Notifications, Share Extension, and More Posted by Jessica Fisher on September 22nd, 2014 [ | Read more »
Starbase Annex (Games)
Starbase Annex 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: "it’s really very clever... a little bit of Hearthstone and a dash of Eclipse" - PocketTactics.com From the creator of Starbase... | Read more »

Price Scanner via MacPrices.net

Apple restocks some refurbished 2014 MacBook...
The Apple Store has restocked some Apple Certified Refurbished 2014 MacBook Airs, with prices starting at $769. An Apple one-year warranty is included with each MacBook, and shipping is free. These... Read more
13-inch 128GB MacBook Air on sale for $949, s...
B&H Photo has the new 2014 13″ 1.4GHz/128GB MacBook Air on sale for $949.99 including free shipping plus NY tax only. Their price is $50 off MSRP. B&H will also include free copies of... Read more
Apple offering free $25 iTunes Gift Card with...
The Apple Store is offering a free $25 iTunes Gift Card with the purchase of a $99 Apple TV for a limited time. Shipping is free. Read more
Apple refurbished iPod touch available for up...
The Apple Store has Apple Certified Refurbished 5th generation iPod touches available starting at $149. Apple’s one-year warranty is included with each model, and shipping is free. Most colors are... Read more
iFixIt Tears Down iPhone 6; Awards Respectabl...
iFixit notes that even the smaller 4.7″ iPhone 6 is a giant among iPhones; so big that Apple couldn’t fit it into the familiar iPhone form factor. In a welcome reversal of a recent trend to more or... Read more
Phone 6 Guide – Tips Book For Both iPhone 6...
iOS Guides has announced its latest eBook: iPhone 6 Guide. Brought to you by the expert team at iOS Guides, and written by best-selling technology author Tom Rudderham, iPhone 6 Guide is packed with... Read more
How to Upgrade iPhone iPad to iOS 8 without D...
PhoneClean, a iPhone cleaner utility offered by iMobie Inc., reveals a solution for upgrading iPhone and iPad to iOS 8 without deleting photos, apps, the new U2 album or anything. Thanks to more than... Read more
Inpaint 6 – Photo Retouching Tool Gets Faster...
TeoreX has announced Inpaint 6, a simple retouching tool for end users that helps remove scratches, watermarks, and timestamps as well as more complex objects like strangers, unwanted elements and... Read more
Worldwide PC Monitor Market Sees Growth in To...
Worldwide PC monitor shipments totaled 32.5 million units in the second quarter of 2014 (2Q14), a year-over-year decline of -2.9%, according to the International Data Corporation (IDC) Worldwide... Read more
Updated Price Trackers
We’ve updated our Mac Price Trackers with the latest information on prices, bundles, and availability on systems from Apple’s authorized internet/catalog resellers: - 15″ MacBook Pros - 13″ MacBook... Read more

Jobs Board

*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
Position Opening at *Apple* - Apple (United...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of Read more
*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
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
Position Opening at *Apple* - Apple (United...
**Job Summary** The Apple Store is a retail environment like no other - uniquely focused on delivering amazing customer experiences. As an Expert, you introduce people Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.