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

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

beaTunes 5.1.13 - Organize your music co...
beaTunes is a full-featured music player and organizational tool for music collections. How well organized is your music library? Are your artists always spelled the same way? Any R.E.M. vs REM?... Read more
ffWorks 1.2.2 - Convert multimedia files...
ffWorks, focused on simplicity, brings a fresh approach to the use of FFmpeg, allowing you to create ultra-high-quality movies without the need to write a single line of code on the command-line.... Read more
OmniPlan 3.12.1 -
With OmniPlan, you can create logical, manageable project plans with Gantt charts, schedules, summaries, milestones, and critical paths. Break down the tasks needed to make your project a success,... Read more
Backblaze 6.1.0.330 - Online backup serv...
Backblaze is an online backup service designed from the ground-up for the Mac. With unlimited storage available for $5 per month, as well as a free 15-day trial, peace of mind is within reach with... Read more
Amazon Chime 4.20.6617 - Communications...
Amazon Chime is a communications service that transforms online meetings with a secure, easy-to-use application that you can trust. Amazon Chime works seamlessly across your devices so that you can... Read more
SyncTwoFolders 2.3.1 - 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
Bartender 3.0.64 - Organize your menu-ba...
Bartender lets you organize your menu-bar apps by hiding them, rearranging them, or moving them to Bartender's Bar. You can display the full menu bar, set options to have menu-bar items show in the... Read more
Slack 3.4.0 - Collaborative communicatio...
Slack is a collaborative communication app that simplifies real-time messaging, archiving, and search for modern working teams. Version 3.4.0: Bug Fixes: Launch (and Hide) on Login now works better... Read more
calibre 3.41.2 - Complete e-book library...
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 librarian... Read more
Persecond 1.4.3 - Timelapse video made e...
Persecond is the easy, fun way to create a beautiful timelapse video. Import an image sequence from any camera, trim the length of your video, adjust the speed and playback direction, and you’re done... Read more

Latest Forum Discussions

See All

Mobile games you probably haven't p...
The App Store is bursting at the seams with all kinds of apps and games of varying quality, but one of the most consistent issues with it is discoverability. Despite having what seems like unlimited money and a full App Store editorial team, Apple... | Read more »
AFK Arena guide - Tips and tricks for be...
AFK Arena may be a less intense form of a gacha game, but that doesn’t mean it’s totally straightforward. As with other games in this genre, there’s a bevy of systems, modes, currencies, etc. that you’ll want to be familiar with as soon as you... | Read more »
Spellsword Cards: Demontide guide - Tips...
Spellsword Cards: Demontide is a wonderful little single-player card game, but it can also be quite unforgiving. Parts of it definitely look and feel like Hearthstone, but you can’t just play this game like its your favorite collectible card game (... | Read more »
The best driving games on iOS
With the recent release of Rush Rally 3, it's easy to be excited about mobile driving games. Figuring out what games in this genre are worth picking up, on the other hand, is a whole other story. [Read more] | Read more »
Construction Simulator returns to Europe...
German publisher astragon Entertainment and developer weltenbauer. SE have just released the third installment of Construction Simulator. Unlike Construction Simulator 2, which was set in the U.S., Construction Simulator 3 returns to its roots in... | Read more »
The best superhero game on mobile
I don't know if you know this, but superheroes are Kind of A Big Deal. Every other week it feels like a new Marvel movie is coming out and the hype train for each release is undeniable. Just look at how the upcoming Avengers: Endgame broke sales... | Read more »
Globesweeper puts a 3D spin on the class...
Long before Minecraft came along to take the crown of 'most played' game, there was another goliath PC game with 'Mine' in its title which held that distinction - Minesweeper. Those with long memories of dial-up broadband and insanely heavy cathode... | Read more »
The stellar open-world skiing game, Gran...
Grand Mountain Adventure, a finalist at the Big Indie Awards 2018, has finally raced its way onto Android. The hugely impressive open-world skiing title hails from Swedish developer Toppluva, a studio made up of 3 snowboarding brothers. New... | Read more »
Onmyoji is celebrating its anniversary w...
NetEase has a deep well to dip into when it comes to sourcing new content for Onmyoji. The game is set during Japan’s Heian period, when elaborate folk tales of spirits – or shikigami – were fire-side favourites. In the world of Onmyoji, though,... | Read more »
The Elder Scrolls: Blades guide - How to...
Were you disappointed by The Elder Scrolls: Blades? You're not alone. It's a bad game that gives off one of the worst first impressions I've ever seen. [Read more] | Read more »

Price Scanner via MacPrices.net

Easter Sale: New 13″ 1.6GHz/128GB Silver MacB...
Amazon is selling the new 2018 13″ 1.6GHz/128GB Silver MacBook Air today for $1079.99 including free shipping. That’s $120 off Apple’s MSRP for this model, and it’s the cheapest price available for a... Read more
Easter Sale: Get an Apple Watch Series 3 for...
Get an Apple Watch Series 3 model for $80 off Apple’s MSRP today on Walmart’s online store. Sale price available for online orders only, in-store prices may vary. Choose free shipping or free local... Read more
Flash Sale: 13″ 2.3GHz Quad-Core MacBook Pros...
Amazon has new 2018 13″ Space Gray 2.3GHz Quad-Core Touch Bar MacBook Pros on sale today for $400-$500 off MSRP, with prices starting at $1399. Shipping is free. These are the same MacBook Pros sold... Read more
Sale! 12″ 1.2GHz Space Gray MacBook for $999...
Amazon has the 12″ 1.2GHz Space Gray Retina MacBook on sale today for $300 off Apple’s MSRP, only $999. Shipping is free: – 12″ 1.2GHz Space Gray MacBook (8GB RAM/256GB SSD): $999.99 $300 off MSRP... Read more
Lowest price on the web: Insta360 Nano Spheri...
Abt Electronics has the popular Insta360 Nano Spherical Video Camera For Apple iPhones, in Champagne, on sale for only $39.99 shipped. That’s a 50% savings over its regular price of $79.99. Read more
Sprint offers 18 month Apple iPhone Xr leases...
Sprint has the new Apple 64GB iPhone Xr available for $15 per month for 18 months for new lines of service. That’s about 50% off the typical monthly rate for this phone. The fine print: “$15/mo.... Read more
These 2018 MacBook Pros at Apple, Certified R...
In the market for a 2018 15″ or 13″ MacBook Pro and looking for the lowest prices you can find? Apple’s refurbished prices are the lowest available for each model from any reseller. An standard Apple... Read more
Save $50-$74 on a new Mac mini today at Abt E...
Abt Electronics has the new 2018 4-Core and 6-Core Mac minis on sale for $50-$74 off Apple’s MSRP, with prices starting at $749. Shipping is free: – 3.6GHz Quad-Core mini: $749 $50 off MSRP – 3.0GHz... Read more
Deal Alert! Amazon is selling the 13″ 2.3GHz/...
Amazon has the 13″ 2.3GHz/256GB Dual-Core non-Touch Bar Space Gray MacBook Pro on sale for $500 off Apple’s MSRP today, only $999. Their price is the cheapest available for this model from any Apple... Read more
Amazon and Walmart have 9.7″ iPads on sale fo...
Amazon is offering new 9.7″ iPads with Apple Pencil Support for $50-$75 off MSRP today, with prices starting at only $249. These are the same iPads found in Apple’s retail and online stores: – 9.7″... Read more

Jobs Board

*Apple* Mobile Master - Best Buy (United Sta...
**688140BR** **Job Title:** Apple Mobile Master **Job Category:** Store Associates **Location Number:** 000114-Fullerton-Store **Job Description:** **What does a Read more
Geek Squad *Apple* Master Consultation Agen...
**681391BR** **Job Title:** Geek Squad Apple Master Consultation Agent **Job Category:** Services/Installation/Repair **Location Number:** 000209-Westminster-Store Read more
Best Buy *Apple* Computing Master - Best Bu...
**688199BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Location Number:** 000535-Portsmouth-Store **Job Description:** **What does a Read more
Farm workers, *Apple* Orchards - Iowa State...
Job ID: 10350093 Job Location:PINE TREE APPLE ORCHARD450 Apple Orchard Rd.White Bear Lake, MN 55110 How to Apply:Mail:MN DEED/FLC#10350093Attn: FLCH2A#19-112332 Read more
*Apple* Mobile Master - Best Buy (United Sta...
**687901BR** **Job Title:** Apple Mobile Master **Job Category:** Store Associates **Location Number:** 000029-Racine-Store **Job Description:** **What does a Best Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.