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

Adobe Premiere Pro 2022 23.1 - Digital v...
Adobe Premiere Pro is available as part of Adobe Creative Cloud for as little as $54.99/month. The price on display is a price for annual by-monthly plan for Adobe Premiere Pro only. Adobe Premiere... Read more
1Password 8.9.10 - Powerful password man...
1Password is a password manager that uniquely brings you both security and convenience. It is the only program that provides anti-phishing protection and goes beyond password management by adding Web... Read more
FotoMagico 6.3 - Powerful slideshow crea...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more
Affinity Photo 1.10.6 - Digital editing...
Affinity Photo - redefines the boundaries for professional photo editing software for the Mac. With a meticulous focus on workflow it offers sophisticated tools for enhancing, editing and retouching... Read more
Vivaldi 5.5.2805.50 - An advanced browse...
Vivaldi is a browser for our friends. We live in our browsers. Choose one that has the features you need, a style that fits and values you can stand by. From the look and feel, to how you interact... Read more
Fantastical 3.7.4 - Create calendar even...
Fantastical is the Mac calendar you'll actually enjoy using. Creating an event with Fantastical is quick, easy, and fun: Open Fantastical with a single click or keystroke Type in your event details... Read more
Adobe Illustrator 2022 27.1 - Profession...
You can download Adobe Illustrator as a part of Creative Cloud for only $20.99/month. Adobe Illustrator is the vector graphics classics in the design industry. It is a digital environment that allows... Read more
Acorn 7.3.1 - Bitmap image editor.
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Apple Configurator 2.16 - Configure and...
Apple Configurator makes it easy to deploy iPad, iPhone, iPod touch, and Apple TV devices in your school or business. Use Apple Configurator to quickly configure large numbers of devices connected to... Read more
Bookends 14.1.5 - Reference management a...
Bookends is a full-featured bibliography/reference and information-management system for students and professionals. Bookends uses the cloud to sync reference libraries on all the Macs you use.... Read more

Latest Forum Discussions

See All

Alchemy Stars celebrates 1 and a half ye...
It has been one and a half years since Alchemy Stars launched, and Level Infinite is celebrating in style with a host of new content. There will be a new story mission and even a store to explore, and a whole new mode for those budding idol... | Read more »
Fighting Game ‘Art of Fighting 2’ ACA Ne...
Last week, side-scrolling shooter Pulstar hit mobile platforms as the newest ACA NeoGeo series release from Hamster and SNK. Read Shaun’s review of it here. Today, fighting game Art of Fighting 2 has launched on iOS and Android. Art of Fighting 2... | Read more »
‘Genshin Impact’ Version 3.3 Update Now...
HoYoverse recently revealed the next major update for Genshin Impact (Free) in the form of version 3.3 ‘All Senses Clear, All Existence Void’. | Read more »
SwitchArcade Round-Up: Reviews Featuring...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 6th, 2022. In today’s article, we’ve got three more reviews. Siralim Ultimate, Astronite, and Swordship get evaluated and scored today. All interesting in their own ways,... | Read more »
‘Pulstar ACA NEOGEO’ Review – Kiss Your...
As I’ve said more than a few times in the past, the NEOGEO was generally known for a couple of genres more than anything else. Fighting games, of course. And thanks to Metal Slug and to a lesser extent Shock Troopers, it’s also known for run-and-gun... | Read more »
‘The Witcher: Monster Slayer’ Shutting D...
Location-based AR game The Witcher: Monster Slayer (Free) from CD Projekt Red’s in-house studio Spokko Games has been getting updated quite often following its launch on iOS and Android. These updates include new challenges, monster types, stamps,... | Read more »
Get Your Hands on the Power Cosmic in th...
To me, my board! As discussed in our story about the last update to the excellent card battler Marvel Snap (Free), the latest season of the game is called The Power Cosmic. | Read more »
HoYoverses announces inaugral art exhibi...
If you are lucky enough to be in the Paris area in early January, then you should pop to the Galerie Joseph and enjoy a look at the world of HoYoverses’ global smash hit, Genshin Impact. There will be unreleased concept art and a deep dive into... | Read more »
SwitchArcade Round-Up: Reviews Featuring...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 5th, 2022. In today’s article, we’ve got a few reviews for you. Square Enix’s Romancing SaGa -Minstrel Song- Remastered, Forever Entertainment’s Front Mission 1st: Remake,... | Read more »
Best iPhone Game Updates: ‘Fire Emblem H...
Hello everyone, and welcome to the week! It’s time once again for our look back at the noteworthy updates of the last seven days. Oh yes, here come the Christmas updates. Quite a lot of the games featured today are doing the holiday thing, with only... | Read more »

Price Scanner via MacPrices.net

Christmas sale at Verizon: Apple AirPods Pro...
Verizon has first-generation Apple AirPods Pro on sale for $159.99 on their online store as part of their continuing Christmas/Holiday sale. Their price is $90 off Apple’s original MSRP, and it’s the... Read more
New Christmas/New Years promo at Xfinity Mobi...
Switch to Xfinity Mobile and open a new line of service, and take $400 off the price of a new iPhone, no trade-in required, through January 10, 2023. The $400 is applied to your account as credits... Read more
Apple iPad Smart Keyboard Folio prices drop u...
Apple iPad Smart Keyboard Folio prices have dropped up to $60 off MSRP at Amazon and Walmart as part of their Christmas/Holiday sales. These are the cheapest prices currently available for these iPad... Read more
Today is the final day for Xfinity Mobile’s $...
If you switch to Xfinity Mobile and open a new line of service, they will take $500 off the price of a new iPhone, no trade-in required. This is the best no trade-in Cyber Monday Apple iPhone 14 deal... Read more
Amazon restocks 10.2″ 64GB 9th-generation iPa...
Amazon has Apple’s 9th generation 10.2″ 64GB WiFi iPads (Silver) in stock and on sale for $269.99 shipped as part of their Christmas/Holiday Sale. Their price is $60 off Apple’s MSRP. Free delivery... Read more
Week’s Best Apple MacBook Air Christmas Sales...
Apple retailers have posted their most-recent Christmas Holiday sale prices on 13″ MacBook Airs. Take up to $150 off MSRP on M2-powered Airs with these sales with prices starting at only $1049. Free... Read more
Open-box 13″ M2 MacBook Pros available for $3...
QuickShip Electronics has open-box return 13″ M2 MacBook Pros in stock and on sale for $300-$350 off MSRP on their eBay store right now, each with free express delivery. According to QuickShip, “The... Read more
Apple is offering $100 iPad discounts to Educ...
Apple will take $100 off 12″ M2 iPad Pros, $50-$100 off 11″ M2 iPad Pros, $50 off iPad Airs, $50 off 8.3″ iPad minis, & $20-$40 off 10″ iPads for all teachers, students, and staff of any... Read more
Midnight Apple Watch Series 8 (41mm GPS + Cel...
Amazon has the Midnight Apple Watch Series 8 (41mm GPS + Cellular) on sale for $50 off MSRP as part of their Holiday sale including free shipping, reducing the price for this Watch to $449.99. Their... Read more
Holiday Sale: Apple Watch Ultra for $50 off M...
Amazon has Apple Watch Ultra models (Alpine Loop, Trail Loop, and Opean Bans) on sale for $50 off MSRP as part of their Holiday sale, each including free shipping, reducing the price for an Ultra to... Read more

Jobs Board

*Apple* Systems Administrator - JAMF - Activ...
…Administration **Duties and Responsibilities** + Configure and maintain the client's Apple Device Management (ADM) solution. The current solution is JAMF supporting Read more
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Mall Read more
Omnichannel Associate - *Apple* Blossom Mal...
Omnichannel Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Sephora Beauty Advisor - *Apple* Blossom Ma...
Sephora Beauty Advisor - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.