TweetFollow Us on Twitter

Nov 95 Challenge
Volume Number:11
Issue Number:11
Column Tag:Programmer’s Challenge

Programmer’s Challenge

By Bob Boonstra, Westford, Massachusetts

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

Enclosing Bounds

The Challenge this month is based on a suggestion by Mike Scanlin, who remains a fan of the column. (We’re still waiting for Mike’s first Challenge entry, however.) The problem is to write a routine that will return a rectangle enclosing all non-white pixels in a selected area of an image. This code might be useful in a drawing or painting program, where the user would be allowed to select a subset of the image by clicking and dragging, and the software would select all of the elements of the image contained within that selection. The prototype of the code you will write is:

void EnclosingBounds(
 PixMapHandle pm,  /* handle to PixMap containing image */
 Rect selection, /* subset of image to enclose */
 Rect *enclosingRect /* enclosing rect return value */
);

Your code should examine all of the pixels within the selection rectangle of the PixMap and return the smallest rectangle containing all of the non-white pixels. Pixels outside the selection rectangle should be ignored. The bounds rectangle of the PixMap will be no larger than 2048 pixels in each dimension, the baseAddr pointer will be longword aligned, and rowBytes will be a multiple of 4. You should deal with pixelSize values of 1, 8, or 32, with values of 8 and 32 being weighted most heavily in measuring performance. For PixMaps with indexed pixels (cmpCount==1), the color table will contain white as the first table entry (as all good color tables are supposed to). For PixMaps with direct pixels, the unused (alpha) bits of each pixel will be zero.

You may use either the Metrowerks or the Symantec compilers for this native PowerPC Challenge. If you have any questions, or would like some test data for your code, please send me e-mail at one of the Programmer’s Challenge addresses, or directly to boonstra@ultranet.com.

Two Months Ago Winner

Congratulations to Eric Lengyel (Blacksburg, VA) for submitting the fastest and smallest entry to the Reversible Scrambling Algorithm Challenge. Despite an unfortunate delay in publication of the magazine that left participants with less time than usual to complete the Challenge, three of the four entries I received by the extended deadline worked correctly, at least in part.

You might recall that the Challenge was to write code that would raise a large integer message to a power and compute the remainder modulo another large integer. The name of the Challenge comes from the fact that this technique is reversible, given properly chosen integers. Eric is a graduate student in Mathematics at Virginia Tech, and he took advantage of a highly optimized multiple precision integer arithmetic library that he had written as part of a number theory project involving the factorization of very large numbers.

Each of the working entries converted the BigNum representation provided in the problem into one that right-justified numbers into a fixed-length data structure. While this imposes a restriction on the maximum size integer that the code can handle, this assumption was permitted by the problem statement. In Eric’s code, the restriction is controlled by a single #define statement.

Eric uses a binary exponentiation algorithm to raise the message to the specified power, and takes advantage of facts from number theory that allow the remainder to be computed at each step of the exponentiation. The time to perform the exponentiation is therefore proportional to the logarithm of the exponent. Eric’s multiplication and division routines use the 68020’s capability to compute the 64-bit product of two longwords and to divide a 64-bit dividend by a longword. The multiplication, division, exponentiation, and compare routines in Eric’s code are general purpose and could be used in any 68K application that needs large integers.

Honorable mention goes to Ernst Munter, who submitted an entry in pure C that was actually the fastest code for the short modulus test cases. Unfortunately, his entry did not produce correct results for the longer moduli.

Here are the times and code sizes for the entries that worked correctly (or partially correctly). Execution time is presented for two specific test cases, with modulus lengths of 22 and 88 bytes, respectively, as well as the total time for all of the test cases I ran. Cases that produced incorrect results are indicated with an asterisk. Numbers in parens after a person’s name indicate that person’s cumulative point total for all previous Challenges, not including this one.

Name time1 time2 Total time code data

(22) (88)
bytes bytes

Eric Lengyel 47 463 2083 1190 0

Xan Gregg (51) 35 967 3175 1558 0

Ernst Munter (C entry) (90) 17 * * 4266 11788

Top 20 Contestants of All Time

Here are the Top 20 Contestants for the Programmer’s Challenges to date. The numbers below include points awarded for this month’s entrants. (Note: ties are listed alphabetically by last name - there are more than 20 people listed this month because of ties.)

Rank Name Points

1. [Name deleted] 176

2. Munter, Ernst 90

3. Karsh, Bill 78

4. Stenger, Allen 65

5. Gregg, Xan 61

6. Larsson, Gustav 60

7. Riha, Stepan 51

8. Goebel, James 49

9. Nepsund, Ronald 47

10. Cutts, Kevin 46

11. Mallett, Jeff 44

12. Kasparian, Raffi 42

13. Vineyard, Jeremy 42

14. Darrah, Dave 31

15. Landry, Larry 29

16. Elwertowski, Tom 24

17. Lee, Johnny 22

18. Noll, Robert 22

19. Anderson, Troy 20

20. Beith, Gary 20

21. Burgoyne, Nick 20

22. Galway, Will 20

23. Israelson, Steve 20

24. Landweber, Greg 20

25. Lengyel, Eric 20

26. Pinkerton, Tom 20

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) 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 2 points

suggesting Challenge 2 points

Here is Eric’s winning solution:

PowerAndRemainder.c

Copyright © 1995 Eric Lengyel
/*
I call my fixed length numbers “BigFixed” and translate from BigNum’s to BigFixed’s in the PowerAndRemainder 
routine.  These are the assembly language routines which are the guts of my program:

(1) PowerMod - raises a number to a power and reduces it by a modulus.  It uses a fast binary exponentiation 
algorithm, reducing by the modulus at each step.
(2) Multiply - multiplies 2 BigNum’s together.
(3) MultQ - mutliplies a BigNum by a long int.
(4) Divide - divides one BigNum by another and supplies the quotient and remainder.
(5) Compare - determines the ordering of 2 BigNum’s.

Some of the loops have been expanded to make more efficient use of the instruction cache.
*/

#define NumSize 72

typedef struct BigNum
{
   short           numDig;
   unsigned char   *dig;
} BigNum;

typedef struct BigFixed
{
   unsigned char   dig[NumSize*4];
} BigFixed;

/* We need 72 longs because the division routine needs the most significant longword to be zero and the 
speed optimization requires that NumSize be a multiple of four. */

void PowerAndRemainder(BigNum *msg, BigNum *exp, BigNum *n,
   BigNum *res);
void PowerMod(BigFixed *msg, BigFixed *exp, BigFixed *n,
   BigFixed *res);
void Multiply(BigFixed *src1, BigFixed *src2, BigFixed *dst);
void MultQ(BigFixed *src1, long src2, BigFixed *dst);
void Divide(BigFixed *end, BigFixed *sor, BigFixed *dst);
short Compare(BigFixed *src1, BigFixed *src2);

PowerAndRemainder

void PowerAndRemainder(BigNum *msg, BigNum *exp, BigNum *n,
   BigNum *res)
{
   short      a, b, numDigits;
   BigFixed   msg0, exp0, n0, res0;
   
   for (a = 0; a < NumSize*4; a++)
   {
      b = NumSize*4 - msg->numDig;
      if (a < b) msg0.dig[a] = 0;
      else msg0.dig[a] = msg->dig[a - b];
      b = NumSize*4 - exp->numDig;
      if (a < b) exp0.dig[a] = 0;
      else exp0.dig[a] = exp->dig[a - b];
      b = NumSize*4 - n->numDig;
      if (a < b) n0.dig[a] = 0;
      else n0.dig[a] = n->dig[a - b];
   }
   PowerMod(&msg0, &exp0, &n0, &res0);
   a = 0;
   while (res0.dig[a] == 0) a++;
   numDigits = res->numDig = NumSize*4 - a;
   for (b = 0; b < numDigits; b++)
      res->dig[b] = res0.dig[a++];
}

PowerMod

void PowerMod(BigFixed *msg, BigFixed *exp, BigFixed *n,
   BigFixed *res)
{
   BigFixed   acc, scrap;

   asm
   {
   LEA      acc, A0            ;   Start with one in
   MOVEQ    #NumSize/4-2, D0   ;   accumulator
1} ; Test a bit in current
                               ;   longword of exponent
   BEQ      @1                 ;   If zero, skip multiply
   PEA      acc                ;   Multiply accumulator
   PEA      acc                ;   by base
   MOVE.L   msg, -(A7)
   JSR      Multiply
   ADDA.W   #12, A7
   MOVE.L   n, -(A7)           ;   Compare accumulator
   PEA      acc                ;   to modulus
   JSR      Compare
   ADDQ.W   #8, A7
   TST.B    D0
   BMI      @1                 ;   If it’s less, skip
                               ;   reduction
   PEA      scrap              ;   Reduce modulo “n”
   MOVE.L   n, -(A7)
   PEA      acc
   JSR      Divide
   ADDA.W   #12, A7
Multiply

/* Multiply src1 by src2 and put product in dst */

void Multiply(BigFixed *src1, BigFixed *src2, BigFixed *dst)
{
   short      topStop, botStop;
   BigFixed   acc, line;
   
   asm
   {
   MOVEM.L  D0-D7/A0-A4, -(A7)
   LEA      acc, A0            ;   Clear accumulator
   MOVEQ    #NumSize/4-1, D0
D5       ;   Do 64-bit multiply
   ADD.L    D2, D5             ;   Add carry to low
                               ;   longword of product
   CLR.L    D2                 ;   Use D2 as dummy to
                               ;   extend carry
   ADDX.L   D2, D6             ;   Add zero to high
                               ;   longword with carry
   MOVE.L   D6, D2             ;   Anything in high
                               ;   longword gets carried
   MOVE.L   D5, 00(A2, D3.W*4) ;   Store low longword in
                               ;   partial product
   SUBQ.W   #1, D3             ;   Loop through all
   CMP.W    topStop, D3        ;   longwords in top number
   BGE      @1
   MOVEA.L  A2, A0             ;   Now add partial product
                               ;   to accumulator
   MOVE.L   D4, D0             ;   Calculate correct
                               ;   position in product
   LEA      acc, A1            ;   Get accumulator’s addr
   ADDQ.W   #1, D0
   ADDA.W   #NumSize * 4, A0
   LSL.W    #2, D0
   ADDA.W   D0, A1
   MOVE.W   D4, D1
   MOVE.L   -(A1), D0          ;   Get longword of product
   SUBQ     #1, D1
   ADD.L    -(A0), D0          ;   Add longword of
   MOVE.L   D0, (A1)           ;   partial product
   TST.W    D1                 ;   If no more longwords,
   BMI      @2                 ;   then branch
MultQ
/* Multiply src1 by src2 and put product in dst */

void MultQ(BigFixed *src1, long src2, BigFixed *dst)
{
   BigFixed   pro;
   
   asm
   {
   MOVEM.L  D0-D7/A0/A1, -(A7)
   LEA      pro, A0            ;   Clear product
   MOVEQ    #NumSize/4-1, D0
D4          ;   Do 64-bit multiply
                               ;   by bottom number
   ADD.L    D2, D4             ;   Add carry
   CLR.L    D2                 ;   Use D2 as dummy to
                               ;   extend carry
   ADDX.L   D2, D5             ;   Add zero with carry
   MOVE.L   D5, D2             ;   High longword
                               ;   becomes carry
   MOVE.L   D4, 00(A1, D0.W*4) ;   Put partial product
                               ;   into result
   SUBQ.W   #1, D0             ;   Loop through all
   CMP.W    D1, D0             ;   longwords in top #
   BGE      @1
Divide

/* Divide end (dividend) by sor (divisor) and put quotient in dst.  Remainder will end
    up in end */

void Divide(BigFixed *end, BigFixed *sor, BigFixed *dst)
{
   long      pq;
   BigFixed  quo, line;
   
   asm
   {
   MOVEM.L  D0-D7/A0-A4, -(A7)
   LEA      quo, A0            ;   Clear quotient
   MOVEQ    #NumSize/4-1, D0
D4          ;   Do 64-bit division
Compare

/* Compare src1 and src2.  Returns 1 if src1 > src2, 0 if they’re equal, and -1 if src1 < 
    rc2. */

short Compare(BigFixed *src1, BigFixed *src2)
{
   asm
   {
   MOVEM.L  D1/D2/A0/A1, -(A7)
   MOVEA.L  src1, A0           ;   Get src1’s address
   MOVEA.L  src2, A1           ;   Get src2’s address
   MOVEQ    #1, D0             ;   Start with +1
   MOVE.L   (A0)+, D2
   CMP.L    (A1)+, D2          ;   Compare 1st longwords
   BLT      @1                 ;   If src1 less, branch
   BNE      @2                 ;   If !=, src1 must
   MOVE.L   (A0)+, D2          ;   be greater
   CMP.L    (A1)+, D2          ;   Cmp 3 more longwords
   BCS      @1                 ;   (Unsigned)
   BNE      @2
   MOVE.L   (A0)+, D2
   CMP.L    (A1)+, D2
   BCS      @1
   BNE      @2
   MOVE.L   (A0)+, D2
   CMP.L    (A1)+, D2
   BCS      @1
   BNE      @2
   MOVEQ    #NumSize/4-2, D1   ;   Number of longwords
                               ;   remaining / 4

 
AAPL
$99.76
Apple Inc.
+2.09
MSFT
$44.08
Microsoft Corpora
+0.45
GOOG
$520.84
Google Inc.
+9.67

MacTech Search:
Community Search:

Software Updates via MacUpdate

Macgo Blu-ray Player 2.10.9.1750 - Blu-r...
Macgo Mac Blu-ray Player can bring you the most unforgettable Blu-ray experience on your Mac. Overview Macgo Mac Blu-ray Player can satisfy just about every need you could possibly have in a Blu-ray... Read more
Apple iOS 8.1 - The latest version of Ap...
The latest version of iOS can be downloaded through iTunes. Apple iOS 8 comes with big updates to apps you use every day, like Messages and Photos. A whole new way to share content with your family.... Read more
TechTool Pro 7.0.5 - Hard drive and syst...
TechTool Pro is now 7, and this is the most advanced version of the acclaimed Macintosh troubleshooting utility created in its 20-year history. Micromat has redeveloped TechTool Pro 7 to be fully 64... Read more
PDFKey Pro 4.0.2 - Edit and print passwo...
PDFKey Pro can unlock PDF documents protected for printing and copying when you've forgotten your password. It can now also protect your PDF files with a password to prevent unauthorized access and/... Read more
Yasu 2.9.1 - System maintenance app; per...
Yasu was originally created with System Administrators who service large groups of workstations in mind, Yasu (Yet Another System Utility) was made to do a specific group of maintenance tasks... Read more
Hazel 3.3 - Create rules for organizing...
Hazel is your personal housekeeper, organizing and cleaning folders based on rules you define. Hazel can also manage your trash and uninstall your applications. Organize your files using a... Read more
Autopano Giga 3.7 - Stitch multiple imag...
Autopano Giga allows you to stitch 2, 20, or 2,000 images. Version 3.0 integrates impressive new features that will definitely make you adopt Autopano Pro or Autopano Giga: Choose between 9... Read more
MenuMeters 1.8 - CPU, memory, disk, and...
MenuMeters is a set of CPU, memory, disk, and network monitoring tools for Mac OS X. Although there are numerous other programs which do the same thing, none had quite the feature set I was looking... Read more
Coda 2.5 - One-window Web development su...
Coda is a powerful Web editor that puts everything in one place. An editor. Terminal. CSS. Files. With Coda 2, we went beyond expectations. With loads of new, much-requested features, a few... Read more
Arq 4.6.1 - Online backup to Google Driv...
Arq is super-easy online backup for the Mac. Back up to your own Google Drive storage (15GB free storage), your own Amazon Glacier ($.01/GB per month storage) or S3, or any SFTP server. Arq backs up... Read more

Latest Forum Discussions

See All

This Week at 148Apps: October 13-17, 201...
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 »
Angry Birds Transformers Review
Angry Birds Transformers Review By Jennifer Allen on October 20th, 2014 Our Rating: :: TRANSFORMED BIRDSUniversal App - Designed for iPhone and iPad Transformed in a way you wouldn’t expect, Angry Birds Transformers is a quite... | Read more »
GAMEVIL Announces the Upcoming Launch of...
GAMEVIL Announces the Upcoming Launch of Mark of the Dragon Posted by Jessica Fisher on October 20th, 2014 [ permalink ] Mark of the Dragon, by GAMEVIL, put | Read more »
Interview With the Angry Birds Transform...
Angry Birds Transformers recently transformed and rolled out worldwide. This run-and-gun title is a hit with young Transformers fans, but the ample references to classic Transformers fandom has also earned it a place in the hearts of long-time... | Read more »
Find Free Food on Campus with Ypay
Find Free Food on Campus with Ypay Posted by Jessica Fisher on October 20th, 2014 [ permalink ] iPhone App - Designed for the iPhone, compatible with the iPad | Read more »
Strung Along Review
Strung Along Review By Jordan Minor on October 20th, 2014 Our Rating: :: GOT NO STRINGSUniversal App - Designed for iPhone and iPad A cool gimmick and a great art style keep Strung Along from completely falling apart.   | Read more »
P2P file transferring app Send Anywhere...
File sharing services like Dropbox have security issues. Email attachments can be problematic when it comes to sharing large files. USB dongles don’t fit into your phone. Send Anywhere, a peer-to-peer file transferring application, solves all of... | Read more »
Zero Age Review
Zero Age Review By Jordan Minor on October 20th, 2014 Our Rating: :: MORE THAN ZEROiPad Only App - Designed for the iPad With its mind-bending puzzles and spellbinding visuals, Zero Age has it all.   | Read more »
Hay Ewe Review
Hay Ewe Review By Campbell Bird on October 20th, 2014 Our Rating: :: SAVE YOUR SHEEPLEUniversal App - Designed for iPhone and iPad Pave the way for your flock in this line drawing puzzle game from the creators of Worms.   | Read more »
My Very Hungry Caterpillar (Education)
My Very Hungry Caterpillar 1.0.0 Device: iOS Universal Category: Education Price: $3.99, Version: 1.0.0 (iTunes) Description: Care for your very own Very Hungry Caterpillar! My Very Hungry Caterpillar will captivate you as he crawls... | Read more »

Price Scanner via MacPrices.net

2013 15-inch 2.0GHz Retina MacBook Pro availa...
B&H Photo has leftover previous-generation 15″ 2.0GHz Retina MacBook Pros now available for $1599 including free shipping plus NY sales tax only. Their price is $400 off original MSRP. B&H... Read more
Updated iPad Prices
We’ve updated our iPad Air Price Tracker and our iPad mini Price Tracker with the latest information on prices and availability from Apple and other resellers, including the new iPad Air 2 and the... Read more
Apple Pay Available to Millions of Visa Cardh...
Visa Inc. brings secure, convenient payments to iPad Air 2 and iPad mini 3as well as iPhone 6 and 6 Plus. Starting October 20th, eligible Visa cardholders in the U.S. will be able to use Apple Pay,... Read more
Textkraft Pocket – the missing TextEdit for i...
infovole GmbH has announced the release and immediate availability of Textkraft Pocket 1.0, a professional text editor and note taking app for Apple’s iPhone. In March 2014 rumors were all about... Read more
C Spire to offer iPad Air 2 and iPad mini 3,...
C Spire on Friday announced that it will offer iPad Air 2 and iPad mini 3, both with Wi-Fi + Cellular, on its 4G+ LTE network in the coming weeks. C Spire will offer the new iPads with a range of... Read more
Belkin Announces Full Line of Keyboards and C...
Belkin International has unveiled a new lineup of keyboard cases and accessories for Apple’s newest iPads, featuring three QODE keyboards and a collection of thin, lightweight folios for both the... Read more
Verizon offers new iPad Air 2 preorders for $...
Verizon Wireless is accepting preorders for the new iPad Air 2, cellular models, for $100 off MSRP with a 2-year service agreement: - 16GB iPad Air 2 WiFi + Cellular: $529.99 - 64GB iPad Air 2 WiFi... Read more
Price drops on refurbished Mac minis, now ava...
The Apple Store has dropped prices on Apple Certified Refurbished previous-generation Mac minis, with models now available starting at $419. Apple’s one-year warranty is included with each mini, and... Read more
Apple refurbished 2014 MacBook Airs available...
The Apple Store has Apple Certified Refurbished 2014 MacBook Airs available for up to $180 off the cost of new models. An Apple one-year warranty is included with each MacBook, and shipping is free.... Read more
Refurbished 2013 MacBook Pros available for u...
The Apple Store has Apple Certified Refurbished 13″ and 15″ MacBook Pros available starting at $929. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.5GHz MacBook Pros (4GB RAM/... 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
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
Position Opening at *Apple* - Apple (United...
**Job Summary** As businesses discover the power of Apple computers and mobile devices, it's your job - as a Solutions Engineer - to show them how to introduce these Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.