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

NeoOffice 2017.14 - Mac-tailored, OpenOf...
NeoOffice is a complete office suite for OS X. With NeoOffice, users can view, edit, and save OpenOffice documents, PDF files, and most Microsoft Word, Excel, and PowerPoint documents. NeoOffice 3.x... Read more
Iridient Developer 3.3.1 - Powerful imag...
Iridient Developer (was RAW Developer) is a powerful image-conversion application designed specifically for OS X. Iridient Developer gives advanced photographers total control over every aspect of... Read more
Google Chrome 70.0.3538.110 - Modern and...
Google Chrome is a Web browser by Google, created to be a modern platform for Web pages and applications. It utilizes very fast loading of Web pages and has a V8 engine, which is a custom built... Read more
Adobe Pepper Flash Player 31.0.0.153 - P...
Adobe Pepper Flash Player is a cross-platform, browser-based application runtime that provides uncompromised viewing of expressive applications, content, and videos across browsers and operating... Read more
Chromium 70.0.3538.110 - 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. Version 70.0.3538.110: Release notes were... Read more
Adobe Flash Player 31.0.0.148 - Plug-in...
Adobe Flash Player is a cross-platform, browser-based application runtime that provides uncompromised viewing of expressive applications, content, and videos across browsers and operating systems.... Read more
Adobe Flash Player 31.0.0.153 - Plug-in...
Adobe Flash Player is a cross-platform, browser-based application runtime that provides uncompromised viewing of expressive applications, content, and videos across browsers and operating systems.... Read more
Tidy Up 5.0.11 - Find duplicate files an...
Tidy Up is a full-featured duplicate finder and disk-tidiness utility. Features Supports Lightroom: it is now possible to search and collect duplicates directly in the Lightroom library. Multiple... Read more
BusyContacts 1.3.1 - Fast, efficient con...
BusyContacts is a contact manager for OS X that makes creating, finding, and managing contacts faster and more efficient. It brings to contact management the same power, flexibility, and sharing... Read more
Reflector 3.2.0 - AirPlay your iOS devic...
Reflector allows you to AirPlay mirror your iPhone or iPad to your Mac. Features Easily demo iOS apps on any Mac running OS X Lion using AirPlay Mirroring on iOS 5. Enable an iPhone or iPad wrapper... Read more

Latest Forum Discussions

See All

Win a brand new iPad courtesy of SEGA an...
Fancy enjoying a blast from the past on an Apple iPad (9.7 inch)? Well now you have the chance to do just that thanks to Pocket Gamer's latest giveaway to celebrate the launch of SEGA Heroes. Developed by the same team behind Marvel® Puzzle Quest,... | Read more »
How will World of Warcraft, Starcraft, a...
You might have heard that Blizzard is bringing Diablo to mobile with Diablo Ultimate. There's been plenty of controversy surrounding that decision, and it's meant that a really important piece of information has been glossed over a little. Namely... | Read more »
Slots Panther Vegas offers a social gamb...
New era of Online gambling Want to try your luck in online social gambling? More and more people are into online casinos as a risk-free amazing way to experience the excitement of a big game. Online casinos and slots machines are gaining popularity... | Read more »
3 features we think you'll love in...
Well known classic RPG “Shin Megami Tensei” franchise originally created by Atlus, can now be played throughout iOS and Android. Created by Sega, “Shin Megami Tensei” has spawned a mobile-centric installment in the shape of “Shin Megami Tensei:... | Read more »
These are the top 3 games for iPhone and...
The end of the week has rolled around again, which means it's time for us to look forward to the games you're going to be playing over the next seven days. We've got the return of a mobile gaming legend next week, as well as a couple of other... | Read more »
Time for you to pick which of these top...
Oh look, Thursday is upon us once more. And we all know what that means! You guessed it, it's time for you to vote for which of these five games you think deserves to win our game of the week award. And have we got a selection for y'all this week... | Read more »
Dragalia Lost - High Midgardsormr Prep G...
It might not seem like there's a ton to do between events in Dragalia Lost, but there is one high level piece of content that can keep you occupied for a long time. Defeating High Midgardsormr is currently the game's most difficult non-event... | Read more »
Get your friends, these are the top 5 be...
You can't be a lone wolf all the time, especially if you want to show off your gaming prowess. And that's where this list comes in - we're running down what we think are the top 5 multiplayer games for iPhone. There might be some controversial... | Read more »
SpitKiss is the worthy winner of last we...
It's been a rough and tumble battle this week, with all of the games managing to get a few hits in where it counts, but after checking with the independent adjudicators at ringside, we can now reveal that gloriously gross smooching sim SpitKiss has... | Read more »
The best games for iPhone - The definiti...
Hi there, and welcome to our ever-increasing list of the very best games for iPhone. We're going to be updating this regularly with new content, so make sure you check back often, because you're not going to want to miss out on even one of the... | Read more »

Price Scanner via MacPrices.net

Sprint offers 32GB 9.7″ iPads with Apple Penc...
Sprint is offering 32GB 9.7″ WiFi + Cellular iPads for only $99.99 when added to your Sprint account. Standard MSRP for these iPads is $459, so their Black Friday week 2018 savings amounts to $360!... Read more
Apple to host four day shopping event this 20...
Apple will be hosting a four day shopping event beginning Friday November 23, 2018 and lasting through Monday November 26th. Special offers will be posted each day, and we will have all the details... Read more
Get a 2018 13″ 4-Core Touch Bar MacBook Pro f...
Apple has Certified Refurbished 2018 13″ 2.3GHz 4-Core Touch Bar MacBook Pros available for $270-$300 off the cost of new models, with prices starting at $1529. Apple’s refurbished prices are the... Read more
Score the best price on Apple’s Macs, iPads,...
Our Apple award-winning price trackers are the best place to look for the best deals and lowest prices on Apple gear this Black Friday and Holiday shopping season. Scan our price trackers for the... Read more
The cheapest price on a 15″ MacBook Pro today...
Save $360 to $420 on the purchase of a 2018 15″ Touch Bar MacBook Pro with these Certified Refurbished models available at Apple. Each model features a new outer case, shipping is free, and an Apple... Read more
Black Friday deal: 12″ 1.3GHz Gold MacBook fo...
Amazon today is has the 12″ 1.3GHz Gold MacBook on sale for $301 off Apple’s price, only $1298 shipped, as part of their Black Friday 2018 week sales: – 12″ 1.3GHz Gold MacBook: $1298 $301 off MSRP... Read more
Score Black Friday Prices On Apple Items Now...
NEWS: 11.19.18- The best bet for anyone shopping for a new shiny Apple product and looking to save the most amount of money going in to this holiday season need not look further than our price... Read more
Save on a new MacBook with these early Black...
B&H Photo has posted early Black Friday sale prices on Apple MacBooks, including up to $300 off MSRP on 15″ MacBook Pros, $100 off new 13″ MacBook Airs, and more. Most of these deals expire... Read more
T-Mobile Black Friday deal: Free iPhone Xr wi...
T-Mobile is offering the 64GB iPhone Xr for free as part of their Black Friday 2018 sale. Two new lines are required, as well as an eligible trade-in (iPhone 6s models or newer). $20.84 is applied to... Read more
Save up to $157 on a 10.5″ iPad Pro with thes...
Apple’s newest authorized reseller, Jet, has 10.5″ iPad Pros on sale for up to $157 off MSRP as part of their Black Friday week sale. Shipping is free. Note that some sale prices may be restricted to... Read more

Jobs Board

*Apple* Mobile Master - Best Buy (United Sta...
**658288BR** **Job Title:** Apple Mobile Master **Job Category:** Store Associates **Location Number:** 000262-Carolina Mall-Store **Job Description:** **What does a Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States- Apple Blossom Mall 1850 Apple Blossom Dr Job ID:1044618 Date:Today Job Read more
Sephora Product Consultant - *Apple* Blosso...
Sephora Product Consultant - Apple Blossom Mall Location:Winchester, VA, United States- Apple Blossom Mall 1850 Apple Blossom Dr Job ID:1056553 Date:Today Job Read more
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States- Apple Blossom Mall 1850 Apple Blossom Dr Job ID:1042611 Date:Today Job Description Read more
Omni-Channel Associate - *Apple* Blossom Ma...
Omni-Channel Associate - Apple Blossom Mall Location:Winchester, VA, United States- Apple Blossom Mall 1850 Apple Blossom Dr Job ID:1074107 Date:Today Job Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.