TweetFollow Us on Twitter

Mar 95 Challenge
Volume Number:11
Issue Number:3
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.

Method Dispatcher

One of the main reasons why I don’t like object oriented languages is because of the inefficiencies the language usually introduces on the runtime code. If you’ve ever traced through a method dispatch routine then you know what I mean (what ever happened to the days of simple, direct JSR’s?). This month you have a chance to write a fast method dispatcher. Who knows? If it’s efficient enough I might just toss my assembler and use your dispatcher with a high level language instead...

The prototype of the function you write is:

typedef unsigned short ushort;
typedef ushort ClassID;
typedef ushort MethodNumber;

MethodAddress
FindMethod(theClassID, theMethodNumber)
ClassID theClassID;
MethodNumbertheMethodNumber;

TheMethodNumber is the number of the method you’re trying to find the address of and theClassID is the ID of the class you want it for. You’ll pass theClassID to a function called GetClassPtr to get a pointer to a Class data structure, which looks like this:

typedef void *MethodAddress;

typedef struct {
 MethodNumber  methodNumber;
 MethodAddress methodAddress;
} MethodEntry;

typedef struct {
 ushort inheritedCount;
 ushort inheritedClasses[15];
 MethodNumber  largestMethodNumber;
 ushort methodCount;
 MethodEntrymethods[];
} Class, *ClassPtr;

The function GetClassPtr will be part of my test bench, although you’ll have to implement at least a rudimentary version of it to test your program (or you can e-mail me for a sample version):

ClassPtr
GetClassPtr(classID)
unsigned short classID;

If GetClassPtr returns -1 (kClassNotFound) then the class cannot be found and your FindMethod routine should return 0 (kMethodNotFound). I will be providing sample data and a sample GetClassPtr function for those who are interested. To get a copy, send me e-mail at scanlin@genmagic.com (internet) or any of the Programmer Challenge addresses listed on page 2.

Once you have a ClassPtr you should look in that class’s methods[] array to see if you can find an entry whose methodNumber is equal to theMethodNumber. Methods[] is a variable-length array (thus, making Class a variable-size structure) containing methodCount number of entries which are sorted smallest to largest by methodNumber. MethodCount is 1-based and is always greater than zero. If you find a match then you should return the corresponding methodAddress.

If you don’t find a match then you should look at the inherited classes (starting with index zero) to see if the method is implemented by one of this class’s superclasses. We support multiple inheritance here and the number of classes we inherit from is stored in inheritedCount (which will be from zero to 15). The class IDs of the classes we inherit from are stored in the inheritedClasses[ ] array. You can pass any of the entries in inheritedClasses to GetClassPtr to get a ClassPtr to that class.

If you can’t find the requested methodNumber in any part of the inheritance tree then FindMethod should return zero (kMethodNotFound).

Here’s a simple example. These 54 bytes (starting at location 0x1000) represent class ID 5:

1000:00000000 00000000 00000000 00000000 
1010:00000000 00000000 00000000 00000000 
1020:00680003 0023AAAA AAAA0057 BBBBBBBB 
1030:0068CCCC CCCC 

The short at location 1000 (inheritedCount) tells us that there are no inherited classes for this class. The short at location 1022 (methodCount) tells us that this class has 3 methods. Methods[0] is from 1024 to 1029; the methodNumber is 23 and the methodAddress is AAAAAAAA (this is just test data to illustrate the structure). Methods[1] is from 102A to 102F and methods[2] is from 1030 to 1035. The short at location 1020 (largestMethodNumber) is equal to the methodNumber of the last MethodEntry in the list (which is the largest methodNumber overall since the list is sorted). In other words, the expression theClassPtr->largestMethodNumber == theClassPtr-> methods[theClassPtr->methodCount-1].methodNumber is always true.

If this class had inherited from class 7 and class 9 then it would have looked like this instead:

1000:00020007 00090000 00000000 00000000 
1010:00000000 00000000 00000000 00000000 
1020:00680003 0023AAAA AAAA0057 BBBBBBBB 
1030:0068CCCC CCCC 

In either case, if you call GetClassPtr(5), since this is class 5 we’re looking at, you would have the value 0x1000 (as type ClassPtr) returned to you.

Since I’ll be calling FindMethod several thousand times with the same set of classes (just like a real runtime system!) you’ll probably want to implement some kind of cache. And since it is desirable for runtime systems to take as little memory as possible, we’re going to have a rule that says your code cannot use more than 16K of memory for its cache (use a static to keep a pointer to it). The total number of methods in the set of classes I’ll be testing with is about 5000, numbered from 1 to 5000. The total number of classes is about 400, numbered from 1 to 400. Those 400 classes will implement an average of 15 methods each and will inherit from an average of 5 other classes (that’s 5 total, once you’ve walked the entire inheritance tree for a particular class). Of course, some methods will be called frequently while others are hardly ever called.

Because this is a little complex, I’m going to give you the brute force way of doing what I’ve described. I’m sure you can do better than this (I’ve used short variable names so that the code will fit in the magazine column):

MethodAddress
FindMethod(cid, mn)
ClassID cid;
MethodNumbermn;
{
 ClassPtr cp;
 MethodAddress addr;
 int    i;
 
 cp = GetClassPtr(cid);
 if (cp == kClassNotFound)
 return kMethodNotFound;
 
 /* look in this class */
 i = 0;
 do {
 if (mn == cp->methods[i].methodNumber)
 return cp->methods[i].methodAddress;
 i++;
 } while (i < cp->methodCount);
 
 /* look in superclasses */
 i = 0;
 while (i < cp->inheritedCount) {
 addr = FindMethod( cp->inheritedClasses[i], mn);
 if (addr != kMethodNotFound)
 return addr;
 i++;
 }
 return kMethodNotFound;
}

E-mail me if you have any questions or if you want the sample data and GetClassPtr function. And if you want to see your name in print all you have to do is either enter a challenge or have me use one of your suggested challenges.

Two Months Ago Winner

Congratulations to Kevin Cutts (Schaumburg, IL) for winning the Poker Hand Evaluator Challenge. And kudos to Gustav Larsson (Mountain View, CA) for being 60% smaller and only about 4% slower than Kevin.

Here are the times and code sizes for each entry. Numbers in parens after a person’s name indicate how many times that person has finished in the top 5 places of all previous Programmer Challenges, not including this one:

Name time code

Kevin Cutts (3) 317 6022

Gustav Larsson 331 2656

Jeff Mallett (3) 331 9428

Ernst Munter (5) 457 2516

Dave Darrah (1) 749 2996

Raffi Kasparian (1) 1230 7394

Kevin wrote four different versions of his BestHand routine; one for every combination of the Booleans wildCardAllowed and straightsAndFlushesValid. That’s a great idea for performance but because of space constraints, we’re only listing the BestHandNoWild version which is for the case where wild cards are not allowed but straights and flushes are valid (which is probably the typical case for poker). The source code to the remaining cases can be found on-line or on this month’s code disk.

Here is Kevin’s winning solution:

January Solution -Poker-

by Kevin M. Cutts

#include <stdlib.h>
#include <stdio.h>

typedef unsigned char Card;

typedef struct SevenCardHand 
{
 Card cards[7];
} SevenCardHand;

typedef struct FiveCardHand
{
 Card cards[5];
} FiveCardHand;

short ComparePokerHands(
 SevenCardHand *, 
 SevenCardHand *,
 FiveCardHand *,
 FiveCardHand *,
 Boolean,
 Card,
 Boolean,
 void *); 

/* Used to remove the suit information and leave only the count from the card */
unsigned char theValue[] = {
0,1,2,3,4,5,6,7,8,9,10,11,12,
0,1,2,3,4,5,6,7,8,9,10,11,12,
0,1,2,3,4,5,6,7,8,9,10,11,12,
0,1,2,3,4,5,6,7,8,9,10,11,12,
};

/* Used to remove card value and leave the suit indicator */
unsigned char theSuit[] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,1,1,1,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,2,2,2,2,2,
3,3,3,3,3,3,3,3,3,3,3,3,3,
};

/* A bit for each card value (aces have two bits) */
unsigned short theValueBit[] = {
0x1000,0x800,0x400,0x200,0x100,0x80,0x40,
 0x20,0x10,0x8,0x4,0x2,0x2001,
0x1000,0x800,0x400,0x200,0x100,0x80,0x40,
 0x20,0x10,0x8,0x4,0x2,0x2001,
0x1000,0x800,0x400,0x200,0x100,0x80,0x40,
 0x20,0x10,0x8,0x4,0x2,0x2001,
0x1000,0x800,0x400,0x200,0x100,0x80,0x40,
 0x20,0x10,0x8,0x4,0x2,0x2001,
};

#define fiveAlike0xa000
#define straightFlush0x9000
#define fourAlike0x8000
#define fullHouse0x7000
#define flush    0x6000
#define straight 0x5000
#define threeAlike 0x4000
#define twoPair  0x3000
#define pair0x2000

#define nonCard 0xff
/* These four functions are custom to handle the four bools wild and flush */
unsigned int BestHandNoWild(SevenCardHand *theHand, 
 FiveCardHand *theBest);
unsigned int BestHand(SevenCardHand *theHand, 
 FiveCardHand *theBest, Card wildCard);
unsigned int BestHandNoFlush(SevenCardHand *theHand, 
 FiveCardHand *theBest, Card wildCard);
unsigned int BestHandNoFlushNoWild(SevenCardHand *theHand, 
 FiveCardHand *theBest);

BestHandNoWild

unsigned int BestHandNoWild(SevenCardHand *theHand, 
 FiveCardHand *theBest)
{
    /* How many of each card value encountered */
 unsigned char handValues[13];
    /* How many of each suit encountered */ 
 unsigned char handSuits[4];
    /* Bit field describing on a suit by suit basis how populated the hand is */ 
 short handRuns[4]; 
 register short i;
 short j;
 Card bestCard, bestPair, goodPair, bestTri, bestQuad;
 Card *cardPtr;
 short runSweep, runResult, runCount;

    /* Zero out all of the counts */
 *(long *)&handValues[0] = 
 *(long *)&handValues[4] = 
 *(long *)&handValues[8] = 
 handValues[12] = 0;
 *(long *)&handSuits[0] = 0;
 *(long *)&handRuns[0] = *(long *)&handRuns[2] = 0;

    /* Now accumulate the values */
 for (i=0, cardPtr=theHand->cards; i<7; i++, cardPtr++)
 {
 handValues[theValue[*cardPtr]]++;
 handSuits[theSuit[*cardPtr]]++;
 handRuns[theSuit[*cardPtr]] |= theValueBit[*cardPtr];
 }
    /* First count the pairs, tris, quads and penta */
 bestCard = bestPair = goodPair = bestTri = bestQuad = nonCard;
 for (i = 12; i >= 0; i--)
 {
 if (!(j = handValues[i])) continue;
 if (j == 4)
 {
 bestQuad = i;
 break;
 }
 if (j == 3 && bestTri == nonCard)
 {
 bestTri = i;
 if (bestPair != nonCard)
 {
 /* Full house */
 break;
 }
 }
 else if (j == 2 && bestPair == nonCard)
 {
 bestPair = i;
 if (bestTri != nonCard)
 {
 /* Full house */
 break;
 }
 }
 else if (j == 2 && goodPair == nonCard)
 {
 goodPair = i;
 }
 else if (bestCard == nonCard)
 {
 bestCard = i;
 }
 }
    /* Now check for a straight flush */
#define CHK_SUIT_NOWILD(suit) \
 if (handSuits[suit] >= 5) \
 { \
 for (runSweep=0x1f;runSweep<0x1fff;runSweep<<= 1) \
 { \
 runResult = handRuns[suit] & runSweep; \
 if (runResult == runSweep) \
 { \
 /* Transfer the five cards */ \
 for (i=0, j=0; j < 5;i++) \
 { \
 if ((theValueBit[theHand->cards[i]] & \
 runSweep && suit == \
 theSuit[theHand->cards[i]])) \
 { \
 theBest->cards[j++] = \
 theHand->cards[i]; \
 } \
 } \
 return straightFlush; \
 } \
 } \
 }
 CHK_SUIT_NOWILD(0);
 CHK_SUIT_NOWILD(1);
 CHK_SUIT_NOWILD(2);
 CHK_SUIT_NOWILD(3);
    /* Next comes four of a kind */
 if (bestQuad != nonCard)
 {
    /* Transfer the five cards */
 runSweep = 1;
 for (i=0, j=0; j < 5;i++)
 {
 if (theValue[theHand->cards[i]] == bestQuad)
 {
 theBest->cards[j++] = theHand->cards[i];
 }
 else if (runSweep)
 {
 theBest->cards[j++] = theHand->cards[i];
 runSweep--;
 }
 }
 return fourAlike | bestQuad;
 }
    /* Next is the full house */
 if (bestTri != nonCard && bestPair != nonCard)
 {
    /* Transfer the five cards */
 for (i=0, j=0; j < 5;i++)
 {
 if (theValue[theHand->cards[i]] == bestTri || 
 theValue[theHand->cards[i]] == bestPair)
 {
 theBest->cards[j++] = theHand->cards[i];
 }
 }
 return fullHouse | (bestTri<<8) | (bestPair);
 }
    /* Now the flush */
#define CHK_FLUSH_NOWILD(suit) \
 if (handSuits[suit] >= 5) \
 { \
    /* Transfer the five cards */ \
 for (i=0, j=0; j < 5;i++) \
 { \
 if (theSuit[theHand->cards[i]] == suit) \
 { \
 theBest->cards[j++] = theHand->cards[i]; \
 } \
 } \
 return flush | bestCard; \
 }
 CHK_FLUSH_NOWILD(0);
 CHK_FLUSH_NOWILD(1);
 CHK_FLUSH_NOWILD(2);
 CHK_FLUSH_NOWILD(3);
    /* Next the straight */
 j = handRuns[0]|handRuns[1]|handRuns[2] | handRuns[3];
 for (runSweep=0x1f; runSweep < 0x1fff; runSweep <<= 1)
 {
 runResult = j & runSweep;
 if (runResult == runSweep)
 {
    /* Transfer the five cards */
 for (i=0, j=0; j < 5;i++)
 {
 if ((theValueBit[theHand->cards[i]] & runSweep))
 {
 theBest->cards[j++] = theHand->cards[i];
 }
 }
 return straight;
 }
 }
    /* and the three of a kind */
 if (bestTri != nonCard)
 {
    /* Transfer the five cards */
 runSweep = 2;
 for (i=0, j=0; j < 5;i++)
 {
 if (theValue[theHand->cards[i]] == bestTri)
 {
 theBest->cards[j++] = theHand->cards[i];
 }
 else if (runSweep)
 {
 theBest->cards[j++] = theHand->cards[i];
 runSweep--;
 }
 }
 return threeAlike | bestTri;
 }
    /* Now two pair */
 if (bestPair != nonCard && goodPair != nonCard)
 {
    /* Transfer the five cards */
 runSweep = 1;
 for (i=0, j=0; j < 5;i++)
 {
 if (theValue[theHand->cards[i]] == bestPair ||
 theValue[theHand->cards[i]] == goodPair)
 {
 theBest->cards[j++] = theHand->cards[i];
 }
 else if (runSweep)
 {
 theBest->cards[j++] = theHand->cards[i];
 runSweep--;
 }
 }
 return twoPair | (bestPair << 8) | goodPair;
 }
    /* And finally a single pair */
 if (bestPair != nonCard)
 {
    /* Transfer the five cards */
 runSweep = 3;
 for (i=0, j=0; j < 5;i++)
 {
 if (theValue[theHand->cards[i]] == bestPair)
 {
 theBest->cards[j++] = theHand->cards[i];
 }
 else if (runSweep)
 {
 theBest->cards[j++] = theHand->cards[i];
 runSweep--;
 }
 }
 return pair | bestPair;
 }
    /* Transfer the five cards */
 runSweep = 4;
 for (i=0, j=0; j < 5;i++)
 {
 if (theValue[theHand->cards[i]] == bestCard)
 {
 theBest->cards[j++] = theHand->cards[i];
 }
 else if (runSweep)
 {
 theBest->cards[j++] = theHand->cards[i];
 runSweep--;
 }
 }
 return bestCard;
}

ComparePokerHands

short ComparePokerHands(
 SevenCardHand *hand1Ptr, 
 SevenCardHand *hand2Ptr,
 FiveCardHand *best1Ptr,
 FiveCardHand *best2Ptr,
 Boolean wildCardAllowed,
 Card wildCard,
 Boolean straightsdAndFlushesValid,
 void *privateDataPtr)
{
 unsigned int hand1Value, hand2Value;
 if (wildCardAllowed && straightsdAndFlushesValid)
 {
 hand1Value = BestHand(hand1Ptr, best1Ptr, wildCard);
 hand2Value = BestHand(hand2Ptr, best2Ptr, wildCard);
 }
 else if (wildCardAllowed)
 {
 hand1Value = BestHandNoFlush(hand1Ptr,best1Ptr,wildCard);
 hand2Value = BestHandNoFlush(hand2Ptr,best2Ptr,wildCard);
 }
 else if (straightsdAndFlushesValid)
 {
 hand1Value = BestHandNoWild(hand1Ptr, best1Ptr);
 hand2Value = BestHandNoWild(hand2Ptr, best2Ptr);
 }
 else
 {
 hand1Value = BestHandNoFlushNoWild(hand1Ptr, best1Ptr);
 hand2Value = BestHandNoFlushNoWild(hand2Ptr, best2Ptr);
 }
 if (hand1Value > hand2Value) return -1;
 if (hand1Value < hand2Value) return 1;
 return 0;
} 

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Latest Forum Discussions

See All

Pack a magnifying glass and practice you...
Somehow it has already been a year since Torchlight: Infinite launched, and XD Games is celebrating by blending in what sounds like a truly fantastic new update. Fans of Cthulhu rejoice, as Whispering Mist brings some horror elements, and tests... | Read more »
Summon your guild and prepare for war in...
Netmarble is making some pretty big moves with their latest update for Seven Knights Idle Adventure, with a bunch of interesting additions. Two new heroes enter the battle, there are events and bosses abound, and perhaps most interesting, a huge... | Read more »
Make the passage of time your plaything...
While some of us are still waiting for a chance to get our hands on Ash Prime - yes, don’t remind me I could currently buy him this month I’m barely hanging on - Digital Extremes has announced its next anticipated Prime Form for Warframe. Starting... | Read more »
If you can find it and fit through the d...
The holy trinity of amazing company names have come together, to release their equally amazing and adorable mobile game, Hamster Inn. Published by HyperBeard Games, and co-developed by Mum Not Proud and Little Sasquatch Studios, it's time to... | Read more »
Amikin Survival opens for pre-orders on...
Join me on the wonderful trip down the inspiration rabbit hole; much as Palworld seemingly “borrowed” many aspects from the hit Pokemon franchise, it is time for the heavily armed animal survival to also spawn some illegitimate children as Helio... | Read more »
PUBG Mobile teams up with global phenome...
Since launching in 2019, SpyxFamily has exploded to damn near catastrophic popularity, so it was only a matter of time before a mobile game snapped up a collaboration. Enter PUBG Mobile. Until May 12th, players will be able to collect a host of... | Read more »
Embark into the frozen tundra of certain...
Chucklefish, developers of hit action-adventure sandbox game Starbound and owner of one of the cutest logos in gaming, has released their roguelike deck-builder Wildfrost. Created alongside developers Gaziter and Deadpan Games, Wildfrost will... | Read more »
MoreFun Studios has announced Season 4,...
Tension has escalated in the ever-volatile world of Arena Breakout, as your old pal Randall Fisher and bosses Fred and Perrero continue to lob insults and explosives at each other, bringing us to a new phase of warfare. Season 4, Into The Fog of... | Read more »
Top Mobile Game Discounts
Every day, we pick out a curated list of the best mobile discounts on the App Store and post them here. This list won't be comprehensive, but it every game on it is recommended. Feel free to check out the coverage we did on them in the links below... | Read more »
Marvel Future Fight celebrates nine year...
Announced alongside an advertising image I can only assume was aimed squarely at myself with the prominent Deadpool and Odin featured on it, Netmarble has revealed their celebrations for the 9th anniversary of Marvel Future Fight. The Countdown... | Read more »

Price Scanner via MacPrices.net

Every model of Apple’s 13-inch M3 MacBook Air...
Best Buy has Apple 13″ MacBook Airs with M3 CPUs in stock and on sale today for $100 off MSRP. Prices start at $999. Their prices are the lowest currently available for new 13″ M3 MacBook Airs among... Read more
Sunday Sale: Apple iPad Magic Keyboards for 1...
Walmart has Apple Magic Keyboards for 12.9″ iPad Pros, in Black, on sale for $150 off MSRP on their online store. Sale price for online orders only, in-store price may vary. Order online and choose... Read more
Apple Watch Ultra 2 now available at Apple fo...
Apple has, for the first time, begun offering Certified Refurbished Apple Watch Ultra 2 models in their online store for $679, or $120 off MSRP. Each Watch includes Apple’s standard one-year warranty... Read more
AT&T has the iPhone 14 on sale for only $...
AT&T has the 128GB Apple iPhone 14 available for only $5.99 per month for new and existing customers when you activate unlimited service and use AT&T’s 36 month installment plan. The fine... Read more
Amazon is offering a $100 discount on every M...
Amazon is offering a $100 instant discount on each configuration of Apple’s new 13″ M3 MacBook Air, in Midnight, this weekend. These are the lowest prices currently available for new 13″ M3 MacBook... Read more
You can save $300-$480 on a 14-inch M3 Pro/Ma...
Apple has 14″ M3 Pro and M3 Max MacBook Pros in stock today and available, Certified Refurbished, starting at $1699 and ranging up to $480 off MSRP. Each model features a new outer case, shipping is... Read more
24-inch M1 iMacs available at Apple starting...
Apple has clearance M1 iMacs available in their Certified Refurbished store starting at $1049 and ranging up to $300 off original MSRP. Each iMac is in like-new condition and comes with Apple’s... Read more
Walmart continues to offer $699 13-inch M1 Ma...
Walmart continues to offer new Apple 13″ M1 MacBook Airs (8GB RAM, 256GB SSD) online for $699, $300 off original MSRP, in Space Gray, Silver, and Gold colors. These are new MacBook for sale by... Read more
B&H has 13-inch M2 MacBook Airs with 16GB...
B&H Photo has 13″ MacBook Airs with M2 CPUs, 16GB of memory, and 256GB of storage in stock and on sale for $1099, $100 off Apple’s MSRP for this configuration. Free 1-2 day delivery is available... Read more
14-inch M3 MacBook Pro with 16GB of RAM avail...
Apple has the 14″ M3 MacBook Pro with 16GB of RAM and 1TB of storage, Certified Refurbished, available for $300 off MSRP. Each MacBook Pro features a new outer case, shipping is free, and an Apple 1-... Read more

Jobs Board

*Apple* Systems Administrator - JAMF - Activ...
…**Public Trust/Other Required:** None **Job Family:** Systems Administration **Skills:** Apple Platforms,Computer Servers,Jamf Pro **Experience:** 3 + years of Read more
IT Systems Engineer ( *Apple* Platforms) - S...
IT Systems Engineer ( Apple Platforms) at SpaceX Hawthorne, CA SpaceX was founded under the belief that a future where humanity is out exploring the stars is Read more
Nurse Anesthetist - *Apple* Hill Surgery Ce...
Nurse Anesthetist - Apple Hill Surgery Center Location: WellSpan Medical Group, York, PA Schedule: Full Time Sign-On Bonus Eligible Remote/Hybrid Regular Apply Now Read more
Housekeeper, *Apple* Valley Village - Cassi...
Apple Valley Village Health Care Center, a senior care campus, is hiring a Part-Time Housekeeper to join our team! We will train you for this position! In this role, Read more
Sublease Associate Optometrist- *Apple* Val...
Sublease Associate Optometrist- Apple Valley, CA- Target Optical Date: Apr 20, 2024 Brand: Target Optical Location: Apple Valley, CA, US, 92307 **Requisition Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.