Coding: Hacks and Snippets

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Coding: Hacks and Snippets

Postby Berengal » Wed Mar 04, 2009 5:41 pm UTC

From the suggestion in the Coding: Fleeting Thoughts thread, here's Coding: Hacks and Snippets.

I made this mainly to just create the thread, but I do have a small hack as well:
Spoiler:

Code: Select all

#!/usr/bin/env ruby

# Useage:
# dictionary = create_wordlist <dictionary file>
# find_anagrams(digest_word(<word or phrase>), dictionary) {|a| puts a}
#
# find_anagrams is an iterator that yields each anagram in turn.
# Note that digest_word also digests spaces, but find_anagrams add them as extras.
# If you want to find anything, you should write your phrase without any spaces.

require 'mathn'

$PRIMES = Prime.new.take 256

def digest_word(word)
  word.each_byte.inject(1) do |a, b| a * $PRIMES[b] end
end

def create_wordlist(dict_file)
  dictionary = Hash.new
  File.open(dict_file).each_line do |word|
    word.chomp!.downcase!
    next if word.length <= 2
    digest = digest_word(word)
    if dictionary[digest].nil?
      dictionary[digest] = []
    end
    dictionary[digest] << word
  end
  return dictionary
end

def find_anagrams(digest, dictionary)
   if digest == 1
      yield ""
      return nil
   end
   dictionary.each do |k, v|
      next if digest % k != 0
      reduced_digest = digest / k
      find_anagrams(reduced_digest, dictionary) do |a|
         v.each {|word| yield word + " " + a}
      end
   end
   return nil
end

It's a hack for two reasons: It's ugly in that it doesn't provide a clean interface nor does it massage its input like it should do. It's also clever in the use of primes and divmod to find anagrams. There you go, both an ugly hack and a clever hack, all in one.

Okay, so maybe an ugly interface doesn't make it an ugly hack unless lots of people start using it, but at least it's clever. I know, because I wrote it.


Now go on you crazy people and post more hacks and snippets, from clever one-liners to dubious casting. With time, effort and luck this thread will turn into SkyNet.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

fazzone
Posts: 186
Joined: Wed Dec 10, 2008 9:38 pm UTC
Location: A boat

Re: Coding: Hacks and Snippets

Postby fazzone » Wed Mar 04, 2009 7:56 pm UTC

My favorite little tidbit is from a card-game project I did a while back; to shuffle a deck of cards I generated a random array of 52 integers, then quicksorted the array, but I applied the same sorting to the deck; i.e. as the array was sorted, the deck was shuffled.
*/

User avatar
You, sir, name?
Posts: 6974
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Coding: Hacks and Snippets

Postby You, sir, name? » Wed Mar 04, 2009 8:08 pm UTC

Fast code for manipulating balanced ternary digits in a native integer. For speed reasons, it doesn't do error checking and it's limited to a word size of 6 (but adding more is trivial) and it should be pretty simple to make it use some other base, by recognizing the pattern of 3^n and floor((3^n)/2) and substituting 3 for 5 or whatever.

Spoiler:

Code: Select all

/* Get the n:th trit in v */
int tritn(int v, int n) {
        if(v >= 0) {
                switch(n) {
                        case 0: return v - 3*((v+1)/3);
                        case 1: return (v+1)/3 - 3*((v+4)/9);
                        case 2: return (v+4)/9 - 3*((v+13)/27);
                        case 3: return (v+13)/27 - 3*((v+40)/81);
                        case 4: return (v+40)/81 - 3*((v+121)/243);
                        case 5: return (v+121)/243 - 3*((v+364)/729);
                   
                } 
        } else {
                switch(n) {
                        case 0: return v + 3*((1-v)/3);
                        case 1: return (v-1)/3 + 3*((4-v)/9);
                        case 2: return (v-4)/9 + 3*((13-v)/27);
                        case 3: return (v-13)/27 + 3*((40-v)/81);
                        case 4: return (v-40)/81 + 3*((121-v)/243);
                        case 5: return (v-121)/243 + 3*((364-v)/729);
                }

        }
        return 0;
}

Code: Select all


/* Set trit n in integer v to t */
int settrit(int v, int n, int t) {
        if(v >= 0) {
                switch(n) {
                        case 0:
                                return t + 3*((v+1)/3);
                        case 1:
                                return v - 3*((v+1)/3 - t) + 9*((v+4)/9);
                        case 2:
                                return v - 9*((v+4)/9 - t) + 27*((v+13)/27);
                        case 3:
                                return v - 27*((v+13)/27 -t) + 81*((v+40)/81);
                        case 4:
                                return v - 81*((v+40)/81 -t) + 243*((v+121)/243);
                        case 5:
                                return v - 243*((v+121)/243 -t) + 729*((v+364)/729);
                }
        } else {
                switch(n) {
                        case 0:
                                return t - 3*((1-v)/3);
                        case 1:
                                return v + 3*((1-v)/3 + t) + 9*((v-4)/9);
                        case 2:
                                return v + 9*((4-v)/9 + t) + 27*((v-13)/27);
                        case 3:
                                return v + 27*((13-v)/27 + t) + 81*((v-40)/81);
                        case 4:
                                return v + 81*((40-v)/81 + t) + 243*((v-121)/243);
                        case 5:
                                return v + 243*((121-v)/243 + t) + 729*((v-364)/729);
                }

        }
        return 0;
}


It's an expansion of an in balanced computing omnipresent function that roughly does to balanced bases what the remainder function does to standard bases
[math]\left\{ \begin{array}{cc}
mod_{b^{\kappa}}\left(n+\left\lfloor \frac{b^{\kappa}}{2}\right\rfloor \right)-\left\lfloor \frac{b^{\kappa}}{2}\right\rfloor & n\ge0\\
-mod_{b^{\kappa}}\left(-n+\left\lfloor \frac{b^{\kappa}}{2}\right\rfloor \right)+\left\lfloor \frac{b^{\kappa}}{2}\right\rfloor & n<0\end{array}\right.[/math]
to
[math]\left\{ \begin{array}{cc}
n-b^{\kappa}\left\lfloor \frac{2n+b^{\kappa}-1}{2b^{\kappa}}\right\rfloor & n\ge0\\
n+b^{\kappa}\left\lfloor \frac{-2n+b^{\kappa}-1}{2b^{\kappa}}\right\rfloor & n<0\end{array}\right.[/math]

(spoiler:ing math screws up the font, sorry about the wall of math)
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

Shriike
Posts: 127
Joined: Mon Jan 26, 2009 3:27 am UTC
Location: Ohio

Re: Coding: Hacks and Snippets

Postby Shriike » Thu Mar 05, 2009 12:41 am UTC

fazzone wrote:My favorite little tidbit is from a card-game project I did a while back; to shuffle a deck of cards I generated a random array of 52 integers, then quicksorted the array, but I applied the same sorting to the deck; i.e. as the array was sorted, the deck was shuffled.

That's pretty clever, it's like the inverse of a matrix.

I think I might steal that trick for myself.
Image

TheRatKing
Posts: 8
Joined: Wed Mar 04, 2009 7:43 pm UTC

Re: Coding: Hacks and Snippets

Postby TheRatKing » Thu Mar 05, 2009 12:45 am UTC

Lately, I have been very interested in creating and drawing fractals. I implemented a couple of fractals using L Systems (Sierpinski's Triangle, Heighway Dragon, and a plant). I also made an interactive program that lets you create fractals using the 'chaos game' method.

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Coding: Hacks and Snippets

Postby phlip » Thu Mar 05, 2009 1:08 am UTC

Shriike wrote:I think I might steal that trick for myself.

I wouldn't recommend it... sorting a list of random numbers is O(n log n) at best, the usual shuffling algorithm is O(n), and also simpler:

Code: Select all

def shuffle(seq):
  l = list(seq)
  for i in xrange(len(l)):
    j = random.randrange(i, len(l))
    l[i], l[j] = l[j], l[i]
  return l


Of course, in Python, you'd just go "from random import shuffle", but that's the algorithm there.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

fazzone
Posts: 186
Joined: Wed Dec 10, 2008 9:38 pm UTC
Location: A boat

Re: Coding: Hacks and Snippets

Postby fazzone » Thu Mar 05, 2009 1:21 am UTC

It's not about efficiency, it's just a really cool idea, and by the nature of the program (card game), an end user would never notice anything even close to that tiny a level of difference in speed. Plus, the fastest code is not always the most elegant, and since speed has no bearing, what's there to lose by shooting for elegance and coolness?
*/

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Coding: Hacks and Snippets

Postby Cosmologicon » Thu Mar 05, 2009 1:39 am UTC

I feel like this thread is going to be full of things like this. Anything you recognize as a hack is likely not to be the best way to do it, but can still be interesting. Maybe we can be a little tolerant of ugly hacks in this thread?

For what it's worth, I just yesterday implemented something very similar in a shell script. This prints out the numbers 1-52 in a random order:

Code: Select all

jot -r -c 416 a z | rs -g 0 8 | cat -n | rev | sort | tr -C -d "0-9\n" | rev

I think this might tie my personal pipe record for one line.

fazzone
Posts: 186
Joined: Wed Dec 10, 2008 9:38 pm UTC
Location: A boat

Re: Coding: Hacks and Snippets

Postby fazzone » Thu Mar 05, 2009 1:54 am UTC

Cosmologicon wrote:

Code: Select all

jot -r -c 416 a z | rs -g 0 8 | cat -n | rev | sort | tr -C -d "0-9\n" | rev

Haha, awesome
*/

mrkite
Posts: 336
Joined: Tue Sep 04, 2007 8:48 pm UTC

Re: Coding: Hacks and Snippets

Postby mrkite » Thu Mar 05, 2009 8:16 am UTC

fazzone wrote:My favorite little tidbit is from a card-game project I did a while back; to shuffle a deck of cards I generated a random array of 52 integers, then quicksorted the array, but I applied the same sorting to the deck; i.e. as the array was sorted, the deck was shuffled.


I did something similar. We had to get a contest form up in 10 minutes... the rules stipulated that 5 random winners would be picked. So I just had the web form submission append your entry as a single line in textfile, prefixed by a random number.

Then to pick the winners I just did

Code: Select all

sort entries | tail -5

User avatar
hotaru
Posts: 1025
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: Coding: Hacks and Snippets

Postby hotaru » Thu Mar 05, 2009 12:12 pm UTC

phlip wrote:sorting a list of random numbers is O(n log n) at best, the usual shuffling algorithm is O(n),

sorting a list of random fixed-size integers is O(n) with radix sort.

Code: Select all

#define SORT(length, numbers) ({ \
  size_t _length = (length); \
  __typeof(numbers[0]) temp[_length], *arrays[2] = {(numbers), temp}; \
  for(size_t i = 0; i < sizeof(temp[0]) * CHAR_BIT; ++i) \
    for(size_t j = 0, start = 0, end = _length - 1; j < _length; ++j){ \
      if(!(arrays[i & 1][j] & 1 << i)) \
        arrays[i & 1 ^ 1][start++] = arrays[i & 1][j]; \
      if(arrays[i & 1][_length - j - 1] & 1 << i) \
        arrays[i & 1 ^ 1][end--] = arrays[i & 1][_length - j - 1]; }})

Code: Select all

factorial product enumFromTo 1
isPrime n 
factorial (1) `mod== 1

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Hacks and Snippets

Postby Xanthir » Thu Mar 05, 2009 1:01 pm UTC

fazzone wrote:My favorite little tidbit is from a card-game project I did a while back; to shuffle a deck of cards I generated a random array of 52 integers, then quicksorted the array, but I applied the same sorting to the deck; i.e. as the array was sorted, the deck was shuffled.

Is the trick that your 52 integers were just that - random integers - and not a random list of the numbers 1-52? If so, then yeah, that qualifies as a clever hack (if a bit inefficient).

My snippet is the range functions I posted about in the Fleeting Thoughts thread. I'm ridiculously happy with these now, for some strange reason.
Spoiler:

Code: Select all

(defmacro range (from clause to &key (by 1))
  "Returns a list of numbers.  You must specify one (and only one) termination
    keyword: upto, below, downto, above, or length."
  (if (atom by)
      (let ((x (gensym)))
        `(loop for ,x from ,from by ,by ,clause ,to collect ,x))
      `(range-pattern ,from ,by ,clause ,to)))
;
(defun range-pattern (start pattern &key repeat upto downto above below)
  "Returns a list of numbers starting with start and incremented
    successively (and circularly) by pattern.  If one of (length, limit)
    is specified, returns a list.  If neither, returns a generator."
  (if (eq :... (or repeat upto downto above below))
      (range-pattern-generator start pattern)
      (loop for diff in (mk-circular pattern)
            for x = (+ start diff) then (+ x diff)
            for i upfrom 1
            until (cond (repeat (= i repeat))
                        (upto (> x upto))
                        (below (>= x below))
                        (downto (< x downto))
                        (above (<= x above)))
            collect x into range
            finally (return (cons start range)))))
;
(defun range-pattern-generator (start pattern)
    (let ((curr start)
            (pattern (mk-circular pattern)))
        (lambda ()
            (let ((return curr))
                (setf curr (+ curr (first pattern)) pattern (rest pattern))
                return))))
;
(defun mk-circular (list)
    (setf (rest (last list)) list))
;
(defun range* (&rest pattern-nums)
  "A simple way to create ranges.
    The first and last numbers passed are the start and end of the range.
    The rest implicitly specify a pattern to be passed to range-pattern.
    Frex, (range* 5 7 11 40) is equivalent to (range-pattern 5 '(2 4) :limit 40).
    Two numbers assumes a pattern of '(1) (or -1, as the situation warrants)."
  (let* ((start (car pattern-nums))
         (end (car (last pattern-nums)))
         (middle (butlast (cdr pattern-nums)))
         (pattern
          (if (null middle)
              (list (sign (- end start)))
              (mapcar '- middle (cons start middle)))))
    (if (eq :... end)
        (range-pattern-generator start pattern)
        (if (< start end)
            (range-pattern start pattern :upto end)
            (range-pattern start pattern :downto end)))))

I was able to simplify them *considerably* when I learned that loop doesn't care if its control words start with a colon or not, so I can reuse the control words passed to range as keywords and pass them to range-pattern directly.

Usage is:
(range 1 :below 5) => (1 2 3 4)
(range 1 :upto 10 :by 3) => (1 4 7 10)
(range 1 :downto -3) => (1 0 -1 -2 -3)
(range 5 :repeat 5 :by '(2 4)) => (5 7 11 13 17)
(range 5 :upto :... :by '(2 4)) => a generating function that produces the same sequence as previous, but forever.

range* emulates and improves upon Haskell's sequence-inference capabilities.

(range* 5 1) => (5 4 3 2 1)
(range* 1 3 10) => (1 3 5 7 9)
(range* 5 7 11 31) => (5 7 11 13 17 19 23 25 29 31)
(range* 5 7 11 :...) => generating function that produces the same sequence, but forever.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Coding: Hacks and Snippets

Postby Berengal » Thu Mar 05, 2009 3:12 pm UTC

Ranges are very important, I agree. I've got a different approach to them however, instead creating list functions whose primary purpose is to operate on ranges, such as {take,drop}EveryNth, merge (a:as b:bs = a:b:merge as bs), mergeSorted{,By}, mergeSortedNoDups{,By} (if the two input lists are sorted, the output is sorted as well. Each element pair is sorted in all cases. NoDups removes duplicates), split ([a] -> ([a], [a])), splitWith ((a->b) -> [a] -> ([a], [b])), separate (takes two numbers n and m, and a list, and returns two lists where it first takes n from the input in the first list, then m from the input in the second list, then n in the first list etc.)

Examples:
takeEveryNth 2 [1,2,3,4,5,6] => [2,4,6]
merge [1,2,3] [4,5,6] => [1,4,2,5,3,6]
mergeSorted [1..5] [3..6] => [1,2,3,3,4,4,5,5,6]
mergeSortedNoDups [1..5] [3..6] => [1,2,3,4,5,6]
split [1,2,3] => ([1,2,3], [1,2,3])
splitWith (+5) [1,2,3] => ([1,2,3], [6,7,8])
separate 1 1 [1,2,3,4,5,6] => ([1,3,5], [2,4,6])
separate 2 4 [1..10] => ([1,2,7,8], [3,4,5,6,9,10])
dropEveryNth 3 [5,7..] => [5,7,11,13,17,19..]

Haskell has lots of functions for manipulating lists based on the properties of their elements, but not that many based on the position of the elements.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Coding: Hacks and Snippets

Postby headprogrammingczar » Thu Mar 05, 2009 3:33 pm UTC

A fun one in Java that isn't at all useful or optimized. If I could get around to learning C(++) and some DirectX, this would make a nice shader though.
Spoiler:

Code: Select all

import java.awt.*;
import java.applet.*;
import java.awt.image.*;

/*
 <applet code="ArtThing.java" height=200 width=200></applet>
 */
public class ArtThing extends Applet implements Runnable {
   Pixel[][] pix = new Pixel[200][200];

   Thread t;

   int i;

   BufferedImage image = new BufferedImage(200, 200,
         BufferedImage.TYPE_INT_RGB);

   Graphics buffer = image.getGraphics();

   public void init() {
      for (int x = 0; x < 200; x++)
         for (int y = 0; y < 200; y++)
            pix[x][y] = new Pixel(x, y);
      t = new Thread(this, "Blur program");
      t.start();
   }

   public void run() {
      i = 50;
      int j = 1;
      float hue = 0.f, saturation = 1.f, brightness = .5f;
      while (1 == 1) {
         if (i == 199 | i == 1)
            j *= -1;
         i += j;
         hue += 1. / 255;
         if (hue >= 1)
            hue = 0;
         for (int x = 1; x < 199; x++) {
            pix[x][i].setColor(Color.getHSBColor(hue, saturation,
                  brightness));
            pix[x][1].setColor(Color.black);
            pix[x][199].setColor(Color.black);
            pix[i][x].setColor(Color.getHSBColor(hue, saturation,
                  brightness));
            pix[1][x].setColor(Color.black);
            pix[199][x].setColor(Color.black);
            pix[x][200 - i].setColor(Color.black);
            pix[200 - i][x].setColor(Color.black);
         }
         for (int x = 1; x < 199; x++)
            for (int y = 1; y < 199; y++) {
               int r = 0, b = 0, g1 = 0;
               r = (int) (.25 * pix[x][y].getColor().getRed() + .09375
                     * pix[x - 1][y - 1].getColor().getRed() + .09375
                     * pix[x][y - 1].getColor().getRed() + .09375
                     * pix[x + 1][y - 1].getColor().getRed() + .09375
                     * pix[x + 1][y].getColor().getRed() + .09375
                     * pix[x + 1][y + 1].getColor().getRed() + .09375
                     * pix[x][y + 1].getColor().getRed() + .09375
                     * pix[x - 1][y + 1].getColor().getRed() + .09375 * pix[x - 1][y]
                     .getColor().getRed());
               b = (int) (.25 * pix[x][y].getColor().getBlue() + .09375
                     * pix[x - 1][y - 1].getColor().getBlue() + .09375
                     * pix[x][y - 1].getColor().getBlue() + .09375
                     * pix[x + 1][y - 1].getColor().getBlue() + .09375
                     * pix[x + 1][y].getColor().getBlue() + .09375
                     * pix[x + 1][y + 1].getColor().getBlue() + .09375
                     * pix[x][y + 1].getColor().getBlue() + .09375
                     * pix[x - 1][y + 1].getColor().getBlue() + .09375 * pix[x - 1][y]
                     .getColor().getBlue());
               g1 = (int) (.25 * pix[x][y].getColor().getGreen() + .09375
                     * pix[x - 1][y - 1].getColor().getGreen() + .09375
                     * pix[x][y - 1].getColor().getGreen() + .09375
                     * pix[x + 1][y - 1].getColor().getGreen() + .09375
                     * pix[x + 1][y].getColor().getGreen() + .09375
                     * pix[x + 1][y + 1].getColor().getGreen() + .09375
                     * pix[x][y + 1].getColor().getGreen() + .09375
                     * pix[x - 1][y + 1].getColor().getGreen() + .09375 * pix[x - 1][y]
                     .getColor().getGreen());
               pix[x][y].setColor(r, g1, b);
            }
         paint(getGraphics());
      }
   }

   public void paint(Graphics g) {
      for (int x = 0; x < 200; x++)
         for (int y = 0; y < 200; y++) {
            buffer.setColor(pix[x][y].getColor());
            buffer.drawLine(pix[x][y].getX(), pix[x][y].getY(), pix[x][y]
                  .getX(), pix[x][y].getY());
         }
      g.drawImage(image, 0, 0, this);
   }

   class Pixel {
      private Point p;

      private Color c;

      public int getX() {
         return p.x;
      }

      public int getY() {
         return p.y;
      }

      public Color getColor() {
         return c;
      }

      public Pixel(int x, int y) {
         p = new Point(x, y);
         c = new Color(0, 0, 0);
      }

      public void setColor(int r, int g, int b) {
         c = new Color(r, g, b);
      }

      public void setColor(Color c) {
         this.c = c;
      }
   }
}

Threading in Java is hella hard, so when I run this, it eats my entire processor.
Edit: the relevant part of the effect is around this line; the rest of it is setting up a pixel array and animation:

Code: Select all

int r = 0, b = 0, g1 = 0;
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

User avatar
Xeio
Friends, Faidites, Countrymen
Posts: 5090
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\
Contact:

Re: Coding: Hacks and Snippets

Postby Xeio » Thu Mar 05, 2009 8:52 pm UTC

headprogrammingczar wrote:
Spoiler:
code
Threading in Java is hella hard, so when I run this, it eats my entire processor.
Edit: the relevant part of the effect is around this line; the rest of it is setting up a pixel array and animation:

Code: Select all

int r = 0, b = 0, g1 = 0;
It probably eats the whole processor (or, one core, on multi-core system) because you don't have any sort of frame rate cap logic. It just draws as fast as possible, all the time.

As for threading in java, it's pretty similar to C# (except java requires a full class implementation, rather than just a single function to run), so I don't think it's all that bad. Threading is probably one of the messier topics in any language though (especially if you aren't sure exactly what you're doing).

Two9A
Posts: 194
Joined: Sat Jul 26, 2008 11:22 pm UTC
Location: The smogbound wastes of northern England
Contact:

Re: Coding: Hacks and Snippets

Postby Two9A » Thu Mar 05, 2009 8:59 pm UTC

I've written before about DSemu, and how full of ugly hacks it is. This is probably among the worst though:

Code: Select all

msb=((v&0xFFFF0000)?(v&0xFF000000)?(v&0xF0000000)?(v&0xC0000000)?(v&0x80000000)?31:30:
(v&0x20000000)?29:28:(v&0x0C000000)?(v&0x08000000)?27:26:(v&0x02000000)?25:24:
(v&0x00F00000)?(v&0x00C00000)?(v&0x00800000)?23:22:(v&0x00200000)?21:20:(v&0x000C0000)?
(v&0x00080000)?19:18:(v&0x00020000)?17:16:(v&0x0000FF00)?(v&0x0000F000)?(v&0x0000C000)
?(v&0x00008000)?15:14:(v&0x00002000)?13:12:(v&0x00000C00)?(v&0x00000800)?11:10:
(v&0x00000200)?9:8:(v&0x000000F0)?(v&0x000000C0)?(v&0x00000080)?7:6:(v&0x00000020)?5:4:
(v&0x0000000C)?(v&0x00000008)?3:2:(v&0x00000002)?1:0);


It gives you the location of the highest set bit in a 32-bit integer, in 5 jumps. One of the old classic hacks, that will always remain ugly.
The Unofficial "Making xkcd Slightly Worse" Archive [Incomplete]: xkcdsw.com
Articles that fall out of my head about once a month: imrannazar.com

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Re: Coding: Hacks and Snippets

Postby Random832 » Thu Mar 05, 2009 10:14 pm UTC

Two9A wrote:I've written before about DSemu, and how full of ugly hacks it is. This is probably among the worst though:

Code: Select all

msb=((v&0xFFFF0000)?(v&0xFF000000)?(v&0xF0000000)?(v&0xC0000000)?(v&0x80000000)?31:30:
(v&0x20000000)?29:28:(v&0x0C000000)?(v&0x08000000)?27:26:(v&0x02000000)?25:24:
(v&0x00F00000)?(v&0x00C00000)?(v&0x00800000)?23:22:(v&0x00200000)?21:20:(v&0x000C0000)?
(v&0x00080000)?19:18:(v&0x00020000)?17:16:(v&0x0000FF00)?(v&0x0000F000)?(v&0x0000C000)
?(v&0x00008000)?15:14:(v&0x00002000)?13:12:(v&0x00000C00)?(v&0x00000800)?11:10:
(v&0x00000200)?9:8:(v&0x000000F0)?(v&0x000000C0)?(v&0x00000080)?7:6:(v&0x00000020)?5:4:
(v&0x0000000C)?(v&0x00000008)?3:2:(v&0x00000002)?1:0);


It gives you the location of the highest set bit in a 32-bit integer, in 5 jumps. One of the old classic hacks, that will always remain ugly.


It only looks ugly because of the way it's written with no whitespace (like whitespace is expensive) - you could showcase the symmetry and efficiency of it with:

Code: Select all

msb=(
    (v&                 0xFFFF0000)?
        (v&             0xFF000000)?
            (v&         0xF0000000)?
                (v&     0xC0000000)?
                    (v& 0x80000000)?
                        31
                    :
                        30
                :
                    (v& 0x20000000)?
                        29
                    :
                        28
            :
                (v&     0x0C000000)?
                    (v& 0x08000000)?
                        27
                    :
                        26
                :
                    (v& 0x02000000)?
                        25
                    :
                        24
        :
            (v&         0x00F00000)?
                (v&     0x00C00000)?
                    (v& 0x00800000)?
                        23
                    :
                        22
                :
                    (v& 0x00200000)?
                        21
                    :
                        20
            :
                (v&     0x000C0000)?
                    (v& 0x00080000)?
                        19
                    :
                        18
                :
                    (v& 0x00020000)?
                        17
                    :
                        16
    :
        (v&             0x0000FF00)?
            (v&         0x0000F000)?
                (v&     0x0000C000)?
                    (v& 0x00008000)?
                        15
                    :
                        14
                :
                    (v& 0x00002000)?
                        13
                    :
                        12
            :
                (v&     0x00000C00)?
                    (v& 0x00000800)?
                        11
                    :
                        10
                :
                    (v& 0x00000200)?
                        9
                    :
                        8
        :
            (v&         0x000000F0)?
                (v&     0x000000C0)?
                    (v& 0x00000080)?
                        7
                    :
                        6
                :
                    (v& 0x00000020)?
                        5
                    :
                        4
            :
                (v&     0x0000000C)?
                    (v& 0x00000008)?
                        3
                    :
                        2
                :
                    (v& 0x00000002)?
                        1
                    :
                        0
);


without changing a single token.

Of course, any code can be made readable by sufficient application of whitespace (and perhaps variable renaming, etc)

Though some do still stretch the definition of "readable"

Code: Select all

_=0,
w=-1,
(*t)(int,int);

a() ??<
    char*p="[gd~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";
    (++w<033)?(
        putchar(
            (*t)(
                w??(p:>,
                w ? _ : 0XD
            )
        ),
        a()
    ) :
        0;
%>

O(x,l) ??<
    _ = '[' / 7;
    return
        !(x%(_-11))?
            x ??' l
        :
            x ^ (1+(++l));
??>
;
main() {
    t=&O;
    w=a();
}
Last edited by Random832 on Thu Mar 05, 2009 10:32 pm UTC, edited 1 time in total.

Rysto
Posts: 1459
Joined: Wed Mar 21, 2007 4:07 am UTC

Re: Coding: Hacks and Snippets

Postby Rysto » Thu Mar 05, 2009 10:25 pm UTC

Two9A wrote:It gives you the location of the highest set bit in a 32-bit integer, in 5 jumps. One of the old classic hacks, that will always remain ugly.

Or, you could just use:

Code: Select all

inline int fsb(uint32_t val)
{
    int ret;
    __asm __volatile("bsrl %1,%0" : "=r" (ret) : "rm" (val));
    return ret;
}


:D

Portability is for suckers.

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: Coding: Hacks and Snippets

Postby Qoppa » Fri Mar 06, 2009 12:02 am UTC

Random832 wrote:Of course, any code can be made readable by sufficient application of whitespace (and perhaps variable renaming, etc)

Though some do still stretch the definition of "readable"

Code: Select all

_=0,
w=-1,
(*t)(int,int);

a() ??<
    char*p="[gd~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";
    (++w<033)?(
        putchar(
            (*t)(
                w??(p:>,
                w ? _ : 0XD
            )
        ),
        a()
    ) :
        0;
%>

O(x,l) ??<
    _ = '[' / 7;
    return
        !(x%(_-11))?
            x ??' l
        :
            x ^ (1+(++l));
??>
;
main() {
    t=&O;
    w=a();
}
Well now that looks familiar. :P Though you can't really call my sig 'any code' since it was intentionally obfuscated. There's a difference between intentionally obfuscated code, and code which was just written/formatted poorly.

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

TheRatKing
Posts: 8
Joined: Wed Mar 04, 2009 7:43 pm UTC

Re: Coding: Hacks and Snippets

Postby TheRatKing » Fri Mar 06, 2009 12:12 am UTC

I've been noodling around with my first obfuscated program (in Python), and came up with something my Algebra 2 teacher would probably enjoy.

Code: Select all

_ = lambda _: chr(int(round((3601.0/39916800.0)         *  _  **  12      \
                          + (-153653.0/19958400.0)      *  _  **  11      \
                          + (118147.0/403200.0)         *  _  **  10      \
                          + (-132253.0/20160.0)         *  _  **  9       \
                          + (116022401.0/1209600.0)     *  _  **  8       \
                          + (-581468113.0/604800.0)     *  _  **  7       \
                          + (24476254069.0/3628800.0)   *  _  **  6       \
                          + (-94127402.0/2835.0)        *  _  **  5       \
                          + (68409807251.0/604800.0)    *  _  **  4       \
                          + (-39030168449.0/151200.0)   *  _  **  3       \
                          + (205696168879.0/554400.0)   *  _  **  2       \
                          + (-183402647.0/616.0)        *  _              \
                          + (99132.0))))
__= _(13)
while __[len(__)-1]!=_(1): __+=(_(ord(_(13))/3+2-len(__)))
print __[::-1]

I changed variable names to further confusion.
The program prints "Hello World!!" I am sure you guys can figure out why.

User avatar
Ephphatha
Posts: 625
Joined: Sat Sep 02, 2006 9:03 am UTC
Location: Bathurst, NSW, Australia

Re: Coding: Hacks and Snippets

Postby Ephphatha » Sat Mar 07, 2009 11:43 am UTC

Time for a horrible hack.

Spoiler:

Code: Select all

void Company::addFromFile(string input)
{   //Ok, this may look messy. Files imported should be saved as
    //comma seperated values, so the first field is the id of the
    //staffmember, the second is the name, the third is the type,
    //and the rest sort of snowball from there.
    //(rate, hours, if a casual, salary if a manager...)
    //now, this section is a bit of a hack. It searchs for the first comma
    //then puts everything before it in a variable, and every after it gets
    //put into the input variable again. rinse, repeat as needed
    int pCC = input.find(",")+1;
    string name = input.substr(0, pCC-1);
    input = input.substr(pCC, input.size()-pCC);
    pCC = input.find(",")+1;
    string type = input.substr(0, pCC-1);
    input = input.substr(pCC, input.size()-pCC);
   
    if (type == "Casual")
    {
        pCC = input.find(",")+1;
        int hours = atoi(input.substr(0, pCC-1).c_str());
        input = input.substr(pCC, input.size()-pCC);
        double rate = atof(input.c_str());
        staff.push_back(new Casual(name, rate, hours));
    }
   
    else if (type == "Intern")
    {
        staff.push_back(new Intern(name));
    }
   
    else if (type == "Janitor")
    {
        pCC = input.find(",")+1;
        int hours = atoi(input.substr(0, pCC-1).c_str());
        input = input.substr(pCC, input.size()-pCC);
        double rate = atof(input.substr(0, pCC-1).c_str());
        input = input.substr(pCC, input.size()-pCC);
        double penalty = atof(input.c_str());
        staff.push_back(new Janitor(name, rate, hours, penalty));
    }
   
    else if (type == "Manager")
    {
        double salary = atof(input.c_str());
        staff.push_back(new Manager(name, salary));
    }
   
    else if (type == "SalesPerson")
    {
        pCC = input.find(",")+1;
        int comission = atoi(input.substr(0, pCC-1).c_str());
        input = input.substr(pCC, input.size()-pCC);
        double sales = atof(input.c_str());
        staff.push_back(new SalesPerson(name, comission, sales));
    }
}


Written for an assignment where I had to save and load data from csv formatted files. Not only did I disobey every standard, it didn't even save the right information to load properly.
I'm not lazy, I'm just getting in early for Christmas is all...

User avatar
Link
Posts: 1327
Joined: Sat Mar 07, 2009 11:33 am UTC
Location: ᘝᓄᘈᖉᐣ
Contact:

Re: Coding: Hacks and Snippets

Postby Link » Sat Mar 07, 2009 12:21 pm UTC

Ah, the wonders of (possibly) CPU-efficient but counter-intuitive code. Python in particular lends itself to that really well.

A method to check if a variable's type is in a given list:

Code: Select all

import operator

def foo(bar):
    baz = (int, float, long, str, unicode)
    return reduce(operator.or_, [isinstance(bar, quux) for quux in baz])

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: Coding: Hacks and Snippets

Postby 0xBADFEED » Sat Mar 07, 2009 2:41 pm UTC

Link wrote:Ah, the wonders of (possibly) CPU-efficient but counter-intuitive code. Python in particular lends itself to that really well.
...snip...

You could just do:

Code: Select all

def foo(bar):
    baz = (int,float,long,str,unicode)
    return any(isinstance(bar,quux) for quux in baz)

This is probably faster than your version.
It only uses a generator expression and the 'any' builtin function. In your version you're building the list of 'isinstance' predicate results regardless if they're necessary. The generator allows you to generate values on-demand. Also,Your 'reduce' is required to reduce the entire list. It doesn't know to bail early if it hits a 'true' value. The 'any' function however only has to look for the first 'true' value. Your method, while clever, is probably one of the slower ways you could do this in Python.
What's wrong with:

Code: Select all

isinstance(bar,baz)

Doodle77
Posts: 107
Joined: Mon Mar 26, 2007 9:46 pm UTC

Re: Coding: Hacks and Snippets

Postby Doodle77 » Sat Mar 07, 2009 4:30 pm UTC

If any of you happen to have a Linksys Analog Telephone Adapter, like the one you get with Earthlink VOIP, this simple script may be useful to you.
callerid.py

Code: Select all

#!/usr/bin/python
import urllib, re, gtk
s = urllib.urlopen("http://<your ATA IP address>/").read()
m = re.search(re.escape("<tr bgcolor=\"#d3d3d3\"><td>Call 1 Peer Name:<td><font color=\"darkblue\">")+"(.*?)"+
      re.escape("</font><td>Call 2 Peer Name:<td><font color=\"darkblue\">")+"(.*?)"+
      re.escape("</font>\n<tr bgcolor=\"#dcdcdc\"><td>Call 1 Peer Phone:<td><font color=\"darkblue\">")+"(.*?)"+
      re.escape("</font><td>Call 2 Peer Phone:<td><font color=\"darkblue\">")+"(.*?)"+
      re.escape("</font>"),s)
s = m.group(1) + " at " + m.group(2) + "\n" + m.group(3) + " at " + m.group(4)
dialog = gtk.MessageDialog(buttons=gtk.BUTTONS_OK)
dialog.set_property("text",s)
def ok_cb(widget, event, data=None):
   gtk.main_quit()
   return False

dialog.connect("response",ok_cb)
dialog.show()
gtk.main()

User avatar
Link
Posts: 1327
Joined: Sat Mar 07, 2009 11:33 am UTC
Location: ᘝᓄᘈᖉᐣ
Contact:

Re: Coding: Hacks and Snippets

Postby Link » Sat Mar 07, 2009 6:28 pm UTC

0xBADFEED wrote:
Link wrote:Ah, the wonders of (possibly) CPU-efficient but counter-intuitive code. Python in particular lends itself to that really well.
...snip...

You could just do:

Code: Select all

def foo(bar):
    baz = (int,float,long,str,unicode)
    return any(isinstance(bar,quux) for quux in baz)

This is probably faster than your version.
It only uses a generator expression and the 'any' builtin function. In your version you're building the list of 'isinstance' predicate results regardless if they're necessary. The generator allows you to generate values on-demand. Also,Your 'reduce' is required to reduce the entire list. It doesn't know to bail early if it hits a 'true' value. The 'any' function however only has to look for the first 'true' value. Your method, while clever, is probably one of the slower ways you could do this in Python.
What's wrong with:

Code: Select all

isinstance(bar,baz)

That's actually possible? Jesus. self.slap(src=self.palm, tgt=self.face) Wow, you learn something new every day :D .

User avatar
Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC

Re: Coding: Hacks and Snippets

Postby Strilanc » Sun Mar 08, 2009 8:34 am UTC

Two9A wrote:I've written before about DSemu, and how full of ugly hacks it is. This is probably among the worst though:

Code: Select all

msb=((v&0xFFFF0000)?(v&0xFF000000)?(v&0xF0000000)?(v&0xC0000000)?(v&0x80000000)?31:30:
(v&0x20000000)?29:28:(v&0x0C000000)?(v&0x08000000)?27:26:(v&0x02000000)?25:24:
(v&0x00F00000)?(v&0x00C00000)?(v&0x00800000)?23:22:(v&0x00200000)?21:20:(v&0x000C0000)?
(v&0x00080000)?19:18:(v&0x00020000)?17:16:(v&0x0000FF00)?(v&0x0000F000)?(v&0x0000C000)
?(v&0x00008000)?15:14:(v&0x00002000)?13:12:(v&0x00000C00)?(v&0x00000800)?11:10:
(v&0x00000200)?9:8:(v&0x000000F0)?(v&0x000000C0)?(v&0x00000080)?7:6:(v&0x00000020)?5:4:
(v&0x0000000C)?(v&0x00000008)?3:2:(v&0x00000002)?1:0);


It gives you the location of the highest set bit in a 32-bit integer, in 5 jumps. One of the old classic hacks, that will always remain ugly.


I can do it in 0 jumps... I think.

Code: Select all

//Returns position of highest bit, starting at 0 for first bit set. Returns 31 if no bits set.
int high_bit(int dword) {
  //reverse bits
  dword = ((dword & 0x0000FFFF) << 16) | ((dword & 0xFFFF0000) >> 16);
  dword = ((dword & 0x00FF00FF) <<  8) | ((dword & 0xFF00FF00) >>  8);
  dword = ((dword & 0x0F0F0F0F) <<  4) | ((dword & 0xF0F0F0F0) >>  4);
  dword = ((dword & 0x33333333) <<  2) | ((dword & 0xCCCCCCCC) >>  2);
  dword = ((dword & 0x55555555) <<  1) | ((dword & 0xAAAAAAAA) >>  1);
  //remove all but lowest bit
  dword &= (dword-1) ^ dword;;
  //get bits of position
  int bit4 = ((dword & 0xFFFF0000) != 0) << 4; //C99 says != returns 1 for true, 0 for false
  int bit3 = ((dword & 0xFF00FF00) != 0) << 3;
  int bit2 = ((dword & 0xF0F0F0F0) != 0) << 2;
  int bit1 = ((dword & 0xCCCCCCCC) != 0) << 1;
  int bit0 = ((dword & 0xAAAAAAAA) != 0) << 0;
  //yay!
  return 31 - (bit0 | bit1 | bit2 | bit3 | bit4);
}


Quite a lot of instructions, but no jumps. Completely untested.
Don't pay attention to this signature, it's contradictory.

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Hacks and Snippets

Postby Xanthir » Sun Mar 08, 2009 2:19 pm UTC

Link wrote:That's actually possible? Jesus. self.slap(src=self.palm, tgt=self.face) Wow, you learn something new every day :D .

Don't worry, I did basically the same thing in Lisp, even creating a short-circuiting version of it for efficiency, until I learned that Lisp, too, has (every), (some), (notevery), and (notany). I felt dumb afterwards.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Re: Coding: Hacks and Snippets

Postby Random832 » Sun Mar 08, 2009 8:26 pm UTC

Strilanc wrote:I can do it in 0 jumps... I think.

Code: Select all

//C99 says != returns 1 for true, 0 for false
If you actually rely on != returning 1 for true rather than simply using it as a truth condition, it'll probably cause a jump.

To actually reduce an arbitrary integer to 1-or-0 with no jumps, you need:

Code: Select all

x = (((unsigned)x)>>16)|x&65535;
x = (x>>8)|x&255;
x = (x>>4)|x&15;
x = (x>>2)|x&3;
x = (x>>1)|x&1;

User avatar
Yakk
Poster with most posts but no title.
Posts: 11052
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Hacks and Snippets

Postby Yakk » Sun Mar 08, 2009 8:39 pm UTC

Or you need a machine language instruction "iszero" and "isnotzero".

If your system has an overflow bit, x&1 | overflowbit(x * (unsigned type)-1) gives you a "is not zero" of 1 without a jump.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Re: Coding: Hacks and Snippets

Postby Random832 » Sun Mar 08, 2009 8:45 pm UTC

Yakk wrote:Or you need a machine language instruction "iszero" and "isnotzero".

If your system has an overflow bit, x&1 | overflowbit(x * (unsigned type)-1) gives you a "is not zero" of 1 without a jump.


In most real machine languages, any instruction that involves a test of any kind (incl. of whether the overflow bit is set) is going to be conditionally jumping rather than setting some register or memory location to 00000000 or 00000001.

mrkite
Posts: 336
Joined: Tue Sep 04, 2007 8:48 pm UTC

Re: Coding: Hacks and Snippets

Postby mrkite » Sun Mar 08, 2009 10:05 pm UTC

If you're going to use assembly, use BSR. Which returns the index of the highest bit set. BSF returns the index of the lowest bit set.

User avatar
PM 2Ring
Posts: 3620
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Coding: Hacks and Snippets

Postby PM 2Ring » Mon Mar 09, 2009 10:45 am UTC

Below is my Tiler program, which I mentioned recently in "Fleeting Thoughts". It's a simple graphics program that lets you make pictures using coloured square & round tiles of various sizes. It has automatic snap-to-grid tile placement and tiles can be rearranged & recoloured. Designs can be saved & reloaded as text files, and saved as PNG images. Brief instructions are included, and further insights may be gained by reading the source code. :)

It should work on any Linux installation < 3 years old, and possibly older. It uses GTK for the GUI. Note that it also requires the gnome.canvas module, which may be hard for Windows users to obtain.

Spoiler:

Code: Select all

#! /usr/bin/env python

# Simple tile layout program
# Derived from the canvas example in the GNOME Developer's Information
# Original author: Jesper Skov <jskov@cygnus.co.uk>

import sys, gtk
from os.path import abspath, dirname
import gnome.canvas
if gtk.pygtk_version < (2, 3, 90):
   print "PyGtk 2.3.90 or later required"
   raise SystemExit

def mainquit(*args):
  gtk.main_quit()

BLOCKSIZE = 16
tname = abspath("tiles.dat")
iname = abspath("tiles.png")

class CanvasExample:
  blocksize = BLOCKSIZE
  gridsize = blocksize

  def __init__(self):
    self.width = 800
    self.height = 600

    # Tile list
    self.all = []

    self.colors = ("red", "orange", "yellow",
      "green", "cyan", "blue", "magenta", "pink", "purple",
      "chocolate", "beige", "black", "grey", "white")

    # File names
    self.tname = tname
    self.iname = iname

  def handle_event(self, widget, event=None):
    if event.type == gtk.gdk.KEY_PRESS:
      key = event.keyval<256 and chr(event.keyval) or event.keyval
      #print key

      # Cycle through colours
      delta = key == "," and -1 or key == "." and 1 or 0
      self.cycle_current_color(widget, delta)
      return gtk.TRUE

    if widget == self.acanvas:
      widget.grab_focus()
      if not self.edittiles and event.type == gtk.gdk.BUTTON_PRESS and event.button == 1:
        # Canvas event
        self.add_object(event.x, event.y)
        return gtk.TRUE
    else:
      if self.edittiles or event.type == gtk.gdk.BUTTON_PRESS:
        # Tile event
        return self.tile_event(widget, event)
    return gtk.FALSE

  def snap(self, x, g=None):
    '''Snap co-ord x to nearest grid point, grid size=g'''
    if g == None:
      g = self.gridsize
    return x - (x%g)

  def tile_event(self, widget, event=None):
    if event.type == gtk.gdk.BUTTON_PRESS:
      if event.button == 1:
        # Remember starting position.
        self.remember_x = self.snap(event.x)
        self.remember_y = self.snap(event.y)
      elif event.button == 2:
        #print "Single press of middle button"
        pass
      elif event.button == 3:
        # Destroy the item.
        widget.destroy()
        self.all.remove(widget)
        #del widget
      return gtk.TRUE

    elif event.type == gtk.gdk._2BUTTON_PRESS:
      #Change the item's color.
      if self.usecurrent:
        self.set_item_color(widget, self.ncolor)
      else:
        delta = (1, -1)[event.button-1]
        self.cycle_item_color(widget, delta)
      return gtk.TRUE

    elif event.type == gtk.gdk.MOTION_NOTIFY:
      if event.state & gtk.gdk.BUTTON1_MASK:
        # Get the new position and move by the difference
        new_x, new_y = self.snap(event.x), self.snap(event.y)
        widget.move(new_x - self.remember_x, new_y - self.remember_y)
        self.remember_x, self.remember_y = new_x, new_y
        return gtk.TRUE

    elif event.type == gtk.gdk.ENTER_NOTIFY:
      # Make the outline wide.
      widget.set(width_units=3)
      return gtk.TRUE

    elif event.type == gtk.gdk.LEAVE_NOTIFY:
      # Make the outline thin.
      widget.set(width_units=1)
      return gtk.TRUE
    return gtk.FALSE

  # Add tile at nearest gridpoint to (x, y)
  def add_object(self, x, y):
    u, v = self.acanvas.get_size()
    u, v = u-self.width, v-self.height
    x, y = self.snap(x-u//2), self.snap(y-v//2)
    x2, y2 = x + self.blocksize, y + self.blocksize
    self.add_obj(self.tiletype, self.ncolor, x, y, x2, y2)
    #print self.tiletype, self.colors[self.ncolor], (x, y, x2, y2)

  # Add tile
  def add_obj(self, tiletype, ncolor, x1, y1, x2, y2):
    w = self.acanvas.root().add(tiletype,
      x1=x1, y1=y1, x2=x2, y2=y2,
      fill_color=self.colors[ncolor], outline_color="black",
      width_units=1.0)
    w.connect("event", self.handle_event)
    w.ncolor = ncolor
    # Add to tile list
    self.all.append(w)

  # Some instructions
  def help(self, widget):
    dialog = gtk.Dialog("Help", self.win, gtk.DIALOG_NO_SEPARATOR)
    label = gtk.Label(
      "Simple tile pattern editor. "
      "Created by PM 2Ring, Oct 2008.\n\n"

      "Left click - add tile. Right click - delete tile.\n\n"

      "When Edit Tiles selected:\nDrag - move tile,\nDouble click - change colour.\n"
      "Left button cycles through colours,\nMiddle button reverse cycles,\n"
      "or select 'Use' to change to current colour.\n\n"

      "Accelerator keys are indicated by an underline\n"
      "and may be pressed with or without ALT.\n"
      "Extra accelerator keys:\n"
      "SPACE: toggle edit.\n"
      "numeric pad: tile size.\n"
      "',' and '.' cycle current colour.\n"
      "k: clear.\n"
      "ESC: quit\n\n"

      "The pattern may be saved and loaded as a text file.\n"
      "The tile image may be saved in PNG format.\n"
      "The Slow button toggles tile by tile pattern loading &\n"
      "clearing to give simple animated draw & erase effects."
      )
    dialog.vbox.pack_start(label, expand=gtk.FALSE)
    label.show()
    dialog.show()

  # Set filename
  def set_fname(self, title, field, action):
    dialog = gtk.FileChooserDialog(title, self.win, action,
      (gtk.STOCK_CANCEL, gtk.RESPONSE_CANCEL, gtk.STOCK_OK, gtk.RESPONSE_OK))
    dialog.set_default_response(gtk.RESPONSE_OK)

    fname = getattr(self, field)
    dialog.set_current_folder(dirname(fname))
    if action == gtk.FILE_CHOOSER_ACTION_SAVE:
      dialog.set_current_name(fname)

    filter = gtk.FileFilter()
    if field == "tname":
      filter.set_name("Tiles")
      filter.add_pattern("*.dat")
    else:
      filter.set_name("Images")
      filter.add_pattern("*.png")
    dialog.add_filter(filter)

    filter = gtk.FileFilter()
    filter.set_name("All files")
    filter.add_pattern("*")
    dialog.add_filter(filter)

    response = dialog.run()
    if response == gtk.RESPONSE_OK:
      setattr(self, field, dialog.get_filename())
    elif response == gtk.RESPONSE_CANCEL:
      print title, "aborted: no file selected"
    dialog.destroy()
    return response == gtk.RESPONSE_OK

  # Save entire list of tiles
  def save(self, widget):
    if not self.set_fname("Save tiles", "tname", gtk.FILE_CHOOSER_ACTION_SAVE): return
    f = open(self.tname, "w")
    #f = sys.stdout
    for i in self.all:
      if isinstance(i, gnome.canvas.CanvasRect): t = "R"
      elif isinstance(i, gnome.canvas.CanvasEllipse): t = "E"
      #else: t = "Unknown[%s]" % type(i)
      #Compensate for width_units
      b = tuple([round(u+v) for u,v in zip(i.get_bounds(), (.5,.5,-.5,-.5))])
      #print "type:%s, colour:%s, bounds:%s" % (t, self.colors[i.ncolor], b)
      f.write("%s %d %s\n" % (t, i.ncolor, b))
    f.close
    print self.tname, "saved"

  # Load tiles from a saved list
  def load(self, widget):
    tiles = {"R" : "GnomeCanvasRect", "E" : "GnomeCanvasEllipse"}
    if not self.set_fname("Load tiles", "tname", gtk.FILE_CHOOSER_ACTION_OPEN): return
    f = open(self.tname, "r")
    try:
      for i in f:
        #Skip blanks & comments
        if len(i)<2 or i[0]=="#":
          continue
        a = i[:-1].split(" ", 2)
        tiletype = tiles[a[0]]
        ncolor = int(a[1])
        bounds = eval(a[2])
        #print a[0], ncolor, bounds
        self.add_obj(tiletype, ncolor, *bounds)
        if self.slow: gtk.main_iteration()
    finally:
      f.close
      print self.tname, "loaded"

  def save_image(self, widget):
    if not self.set_fname("Save image", "iname", gtk.FILE_CHOOSER_ACTION_SAVE): return
    self.win.present()

    # Delay until Canvas window is redrawn. Surely there's a better way!
    f = 0
    for i in xrange(100):
      gtk.main_iteration()
      f += self.win.has_focus
      p = gtk.events_pending()
      #print i, f, p
      if f and not p: break

    width, height = self.acanvas.get_size()
    pixbuf = gtk.gdk.Pixbuf(gtk.gdk.COLORSPACE_RGB, False, 8, width, height)
    pixbuf.get_from_drawable(self.acanvas.bin_window, self.acanvas.get_colormap(),
      0,0, 0,0, width, height)
    pixbuf.save(self.iname, "png")
    print self.iname, "saved"

  # Clear entire list of tiles
  def clear(self, widget):
    self.all.reverse()
    for i in self.all:
      i.destroy()
      if self.slow: gtk.main_iteration()
      del i
    self.all = []

  # Set self attribute 'name' to value. Use value=None for ToggleButtons
  def set_attr(self, widget, name, value=None):
    if value == None:
      value = widget.get_active()
    setattr(self, name, value)

  def cycle_item_color(self, item, delta):
    # Pick next color from the list.
    l = len(self.colors)
    self.set_item_color(item, (item.ncolor + l + delta) % l)

  def cycle_current_color(self, widget, delta):
    # Pick next color from the list.
    l = len(self.colors)
    self.newcolor(widget, (self.ncolor + l + delta) % l)

  def set_item_color(self, item, ncolor):
    item.ncolor = ncolor
    item.set(fill_color = self.colors[ncolor])

  def newcolor(self, widget, ncolor):
    self.ncolor = ncolor
    self.drawingarea.modify_bg(gtk.STATE_NORMAL, self.acolors[ncolor])

  def main(self):
    # Open window to hold canvas.
    self.win = win = gtk.Window()
    win.connect("destroy", mainquit)
    win.set_title("Simple Tiler")

    # Pre-allocate palette colors
    #self.acolors = map(win.get_colormap().alloc_color, self.colors)
    self.acolors = tuple([win.get_colormap().alloc_color(i) for i in self.colors])

    # Current color number
    self.ncolor = 0

    # Use Current color number when editing
    self.usecurrent = False

    #Current tile object type
    self.tiletype = "GnomeCanvasRect"

    #False to add tiles, true to edit them
    self.edittiles = False

    #False for normal load & clear, true to do them tile by tile
    self.slow = False

    # Set up handler for keyboard shortcuts
    accel_group = gtk.AccelGroup()
    win.add_accel_group(accel_group)

    def accel(button, key):
      '''Add accelerator for key code to button'''
      button.add_accelerator("clicked", accel_group, key, 0, gtk.ACCEL_VISIBLE)

    # Create VBox to hold canvas and buttons.
    vbox = gtk.VBox()
    win.add(vbox)

    # Create canvas.
    self.acanvas = gnome.canvas.Canvas()
    self.acanvas.set_size_request(self.width, self.height)
    self.acanvas.set_scroll_region(0,0, self.width, self.height)
    self.acanvas.connect("event", self.handle_event)
    self.acanvas.set_events(gtk.gdk.BUTTON_PRESS_MASK | gtk.gdk.KEY_PRESS_MASK)
    vbox.pack_start(self.acanvas)

    # Add a separator bar, below the canvas
    separator = gtk.HSeparator()
    vbox.pack_start(separator, expand=gtk.FALSE)

    # Create palette buttons.
    hbox = gtk.HBox()
    vbox.pack_start(hbox, expand=gtk.FALSE)

    b = gtk.ToggleButton("_Use")
    b.connect("clicked", self.set_attr, "usecurrent")
    accel(b, ord("u"))
    hbox.pack_start(b)

    # Create drawingarea to display current color
    self.drawingarea = gtk.DrawingArea()
    self.drawingarea.set_size_request(50, 10)
    self.drawingarea.modify_bg(gtk.STATE_NORMAL, self.acolors[0])
    hbox.pack_start(self.drawingarea)

    # Add a separator bar, before the color buttons
    separator = gtk.VSeparator()
    hbox.pack_start(separator, expand=gtk.FALSE)

    for i, c in enumerate(self.acolors):
      b = gtk.Button(self.colors[i][:5])
      #b = gtk.Button(" ")
      b.connect("clicked", self.newcolor, i)
      b.modify_bg(gtk.STATE_NORMAL, c)
      hbox.pack_start(b)

    # Add a separator bar, below the palette
    separator = gtk.HSeparator()
    vbox.pack_start(separator, expand=gtk.FALSE)

    hbox = gtk.HBox()
    vbox.pack_start(hbox, expand=gtk.TRUE)

    # Create size buttons.
    vbox1 = gtk.VBox()
    hbox.pack_start(vbox1, expand=gtk.FALSE)

    hbox1 = gtk.HBox()
    vbox1.pack_start(hbox1, expand=gtk.TRUE)

    label = gtk.Label("Tile size")
    hbox1.pack_start(label, expand=gtk.TRUE)

    b = None
    for i in range(1,7):
      b = gtk.RadioButton(b, "%d" % i)
      b.connect("clicked", self.set_attr, "blocksize", i*BLOCKSIZE)
      # Numpad accelerators
      accel(b, i + gtk.keysyms.KP_0)
      hbox1.pack_start(b, expand=gtk.FALSE)

    # Add a separator bar, between the size buttons
    separator = gtk.HSeparator()
    vbox1.pack_start(separator, expand=gtk.FALSE)

    hbox1 = gtk.HBox()
    vbox1.pack_start(hbox1, expand=gtk.TRUE)

    label = gtk.Label("Grid size")
    hbox1.pack_start(label, expand=gtk.TRUE)

    b = None
    for i in range(1,7):
      b = gtk.RadioButton(b, "%d" % i)
      b.connect("clicked", self.set_attr, "gridsize", i*BLOCKSIZE)
      hbox1.pack_start(b, expand=gtk.FALSE)

    # Add a separator bar, after the size buttons
    separator = gtk.VSeparator()
    hbox.pack_start(separator, expand=gtk.FALSE)

    vbox1 = gtk.VBox()
    hbox.pack_end(vbox1, expand=gtk.TRUE)

    # Create control buttons.
    hbox = gtk.HBox()
    vbox1.pack_start(hbox, expand=gtk.TRUE)

    label = gtk.Label("Tile shape")
    hbox.pack_start(label)

    b = gtk.RadioButton(None, "_Square")
    b.connect("clicked", self.set_attr, "tiletype", "GnomeCanvasRect")
    accel(b, ord("s"))
    hbox.pack_start(b)

    b = gtk.RadioButton(b, "_Circle")
    b.connect("clicked", self.set_attr, "tiletype", "GnomeCanvasEllipse")
    accel(b, ord("c"))
    hbox.pack_start(b)

    b = gtk.ToggleButton("Slo_w")
    accel(b, ord("w"))
    b.connect("clicked", self.set_attr, "slow")
    hbox.pack_start(b)

    hbox = gtk.HBox()
    vbox1.pack_start(hbox, expand=gtk.TRUE)

    b = gtk.ToggleButton("_Edit Tiles")
    accel(b, ord("e"))
    accel(b, ord(" "))
    b.connect("clicked", self.set_attr, "edittiles")
    hbox.pack_start(b)

    b = gtk.Button("Clear")
    b.connect("clicked", self.clear)
    accel(b, ord("k"))
    hbox.pack_start(b)

    b = gtk.Button("_Load")
    b.connect("clicked", self.load)
    accel(b, ord("l"))
    hbox.pack_start(b)

    b = gtk.Button("S_ave")
    b.connect("clicked", self.save)
    accel(b, ord("a"))
    hbox.pack_start(b)

    b = gtk.Button("Save _Image")
    b.connect("clicked", self.save_image)
    accel(b, ord("i"))
    hbox.pack_start(b)

    b = gtk.Button("_Help")
    b.connect("clicked", self.help)
    accel(b, ord("h"))
    hbox.pack_start(b)

    b = gtk.Button("_Quit")
    b.connect("clicked", mainquit)
    accel(b, gtk.keysyms.Escape)
    accel(b, ord("q"))
    hbox.pack_start(b)

    win.show_all()

if __name__ == "__main__":
  CanvasExample().main()
  gtk.main()

User avatar
PM 2Ring
Posts: 3620
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Coding: Hacks and Snippets

Postby PM 2Ring » Sun Mar 22, 2009 3:58 am UTC

Here's a python program that converts to & from Roman numerals. There are possibly better ways to do this, and the program could use more error checking, but at least it works. :)

Code: Select all

#! /usr/bin/env python

''' Roman numeral conversions '''

import sys

rom = 'ivxlcdm'
dec = [1, 5, 10, 50, 100, 500, 1000]
decv = dict(zip(rom, dec))

def romantodec(r):
  ''' Convert Roman numeral r to integer '''
  s = 0
  w = len(r) 
  for i in xrange(w):
    d = decv.get(r[i], 0)
    if d==0:
      print >>sys.stderr, 'Warning: %s is not a valid Roman numeral' % r[i]
      continue
      #return s
   
    if i<w-1 and decv.get(r[i+1], 0) > d:
      d = -d
    s += d
  return s

def dectoroman(n):
  ''' Convert integer n to Roman numeral '''
  if not isinstance(n, (int, long)):
    print >>sys.stderr, '%s is not an integer' % n
    return ''
  if n<1 or n>=4000:
    print >>sys.stderr, '%d is out of range [1 - 4000]' % n
    return ''
     
  s = str(n)
  w = len(s)
  r = []
  for i in xrange(w):
    a = int(s[w - i - 1])   
    if a<5:
      if a<4:
        r = a*[rom[2*i]] + r
      else:
        r = [rom[2*i:2*i+2]] + r
    else:
      a -= 5     
      if a<4:
        r = [rom[2*i+1]] + a*[rom[2*i]] + r
      else:
        r = [rom[2*i]] + [rom[2*i+2]] + r       
  return ''.join(r)

def testall(n):
  a = True   
  for i in xrange(1, n):
    r = dectoroman(i)
    d = romantodec(r)
    b = i==d
    a = a and b     
    #print i, r, d, b
  print ('Error!', 'All OK')[a]
   
def main():
  if len(sys.argv) <= 1:
    print >>sys.stderr, '''Convert decimals to roman numerals, or vice versa
    Usage: %s {int | roman}''' % sys.argv[0]
    sys.exit(1) 

  #Check if all elements of s are in t
  def check(s, t):
    return reduce(lambda x, y: x and y in t, s, True)
   
  digits = '0123456789'
  for s in sys.argv[1:]:
    s = s.lower()
    if check(s, digits):
      print dectoroman(int(s)), 
    elif check(s, rom):
      print romantodec(s),
    else:
      print s, 
 
if __name__ == '__main__':
  main()
  #testall(4000) 


Thanks, Hotaru.
Last edited by PM 2Ring on Sun Mar 22, 2009 5:06 am UTC, edited 1 time in total.

User avatar
hotaru
Posts: 1025
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: Coding: Hacks and Snippets

Postby hotaru » Sun Mar 22, 2009 4:34 am UTC

PM 2Ring wrote:

Code: Select all

  if not isinstance(n, int):
    print >>sys.stderr, '%s is not an integer' % n
    return ''
  if n<1 or n>=4000:
    print >>sys.stderr, '%d is out of range [1 - 4000]' % n
    return ''
2971215073 is not an integer

just thought i'd point that out...
maybe you should do isinstance(n, (int, long)) instead. that way the error message makes more sense, and if you ever call it with a long in the range 1-4000 it'll still work, instead of doing this:

Code: Select all

>>> dectoroman(2010L)
2010 is not an integer
''

Code: Select all

factorial product enumFromTo 1
isPrime n 
factorial (1) `mod== 1

User avatar
Earlz
Gets Obvious Implications
Posts: 785
Joined: Sat Jun 09, 2007 8:38 am UTC
Location: USA
Contact:

Re: Coding: Hacks and Snippets

Postby Earlz » Sun Mar 22, 2009 9:42 pm UTC

This code was in my operating system, AlloyOS...
Spoiler:

Code: Select all

/**This is one heck of a function, but it works quite well...
This function takes the assembly routine, int_template and copies it
into malloc'd memory and makes small modifications(as well as adding a bit of code in hex)
to make it so that C functions can tell what interrupt was called and what not
note, this should only be used once for each interrupt number, and should only be used during init**/
void *CreateInterruptStub(uint8_t num, uint8_t type){
   char *tmp;
   switch(type){
      case INTERRUPT_NORMAL:
         tmp=malloc(int_template_size+4);
         memset(tmp,0x90,int_template_size+4);
         tmp[0]=0x6A;
         tmp[1]=0x00; //mean push 0, this is for a dummy error code
         tmp[2]=0x6A;
         tmp[3]=num; //means push <num> this is for interrupt number.
         memcpy((void*)&tmp[4],(void*)&int_template,int_template_size);
         
      break;
      case INTERRUPT_NO_ERR:
         tmp=malloc(int_template_size+2);
         memset(tmp,0x90,int_template_size+2);
         tmp[0]=0x6A;
         tmp[1]=num;
         memcpy((void*)&tmp[2],(void*)&int_template,int_template_size);
      break;
      case INTERRUPT_IRQ_M:
         tmp=malloc(int_template_size+7);
         memset(tmp,0x90,int_template_size+7);
         tmp[0]=0x6A;
         tmp[1]=0x00; //mean push 0, this is for a dummy error code
         tmp[2]=0x6A;
         tmp[3]=num; //means push <num> this is for interrupt number.
         memcpy((void*)&tmp[4],(void*)&int_template,int_template_size);
         tmp[int_template_size+4-1]=0xB0; //mov al,0x20 --this actually overwrites the iret in int_template
         tmp[int_template_size+4+0]=0x20; //^
         tmp[int_template_size+4+1]=0xE6; //out 0x20,al
         tmp[int_template_size+4+2]=0x20; //^
         tmp[int_template_size+4+3]=0xCF; //iret
      break;
      case INTERRUPT_IRQ_S:
         tmp=malloc(int_template_size+9);
         memset(tmp,0x90,int_template_size+9);
         tmp[0]=0x6A;
         tmp[1]=0x00; //mean push 0, this is for a dummy error code
         tmp[2]=0x6A;
         tmp[3]=num; //means push <num> this is for interrupt number.
         memcpy((void*)&tmp[4],(void*)&int_template,int_template_size);
         tmp[int_template_size+4-1]=0xB0; //mov al,0x20 --this actually overwrites the iret in int_template
         tmp[int_template_size+4+0]=0x20; //^
         tmp[int_template_size+4+1]=0xE6; //out 0xA0,al
         tmp[int_template_size+4+2]=0xA0; //^
         tmp[int_template_size+4+3]=0xE6; //out 0x20,al
         tmp[int_template_size+4+4]=0x20; //^
         tmp[int_template_size+4+5]=0xCF; //iret
      break;
      default:
         return NULL;
      break;
   }
   return tmp;
}


...The assembly routine
int_template: ;compiled once but edited and used as a template
;   push byte 0 ;error code
;   push byte 0 ;interrupt number
   pusha
   push ds
   push es
   push fs
   push gs
   mov ax, 0x08   ; Load the Kernel Data Segment descriptor!
   mov ds, ax
   mov es, ax
   mov fs, ax
   mov gs, ax
   mov ss,ax
   mov ebx, esp   ; Push us the stack
   mov eax,0
   mov al,byte [int_level]
   shl eax,12 ;align it to a page
   or eax,INT0_STACK_BASE
   inc byte [int_level]
   mov esp,eax
   push ebx
   mov eax, int_catcher ;this stays constant
   call eax   ; A special call, preserves the 'eip' register
   
   pop esp
   dec byte [int_level]
   ;pop eax
   
   pop gs
   pop fs
   pop es
   pop ds
   popa
   add esp, 8     ; Cleans up the pushed error code and pushed ISR number
   iret           ; pops 5 things at once: CS, EIP, EFLAGS, SS, and ESP!
end_template:
int_template_size: dd (end_template-int_template)

My new blag(WIP, so yes it's still ugly..)
DEFIANCE!
Image
This is microtext. Zooming in digitally makes it worse. Get a magnifying glass.. works only on LCD

mrkite
Posts: 336
Joined: Tue Sep 04, 2007 8:48 pm UTC

Re: Coding: Hacks and Snippets

Postby mrkite » Mon Apr 27, 2009 5:47 pm UTC

For some unknown reason, I had the sudden and uncontrollable urge to write this:

Code: Select all

for (i=0;i<8;i++)
{
    d[i]=a[i]^b[i]^c;
    c=((a[i]|b[i])&c)|(a[i]&b[i]);
}


I won't spoil it, but I will say two things: One, this is the absolute worst way to do this. Two, when you go deep enough, this is how everyone does it.

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Re: Coding: Hacks and Snippets

Postby Random832 » Mon Apr 27, 2009 6:38 pm UTC

mrkite wrote:For some unknown reason, I had the sudden and uncontrollable urge to write this:

Code: Select all

for (i=0;i<8;i++)
{
    d[i]=a[i]^b[i]^c;
    c=((a[i]|b[i])&c)|(a[i]&b[i]);
}


I won't spoil it, but I will say two things: One, this is the absolute worst way to do this. Two, when you go deep enough, this is how everyone does it.


Spoiler:
It's a binary adder for eight bits. And at the low level it actually happens you can't really say it's the worst way to do it, because if there _were_ a better way to do it it would be used.

mrkite
Posts: 336
Joined: Tue Sep 04, 2007 8:48 pm UTC

Re: Coding: Hacks and Snippets

Postby mrkite » Mon Apr 27, 2009 8:54 pm UTC

Random832 wrote:
Spoiler:
It's a binary adder for eight bits. And at the low level it actually happens you can't really say it's the worst way to do it, because if there _were_ a better way to do it it would be used.


Yeah, I was going to say "unless you have a soldering iron in your hand, this is the worst way to do it" :)

On a related note, I was thinking about how much extra work you have to do in an emulator because you don't have C, N, V, or other flags in high level languages. For things like addition, you either have to use a larger operand size than the one you are emulating, or you have to do the addition twice and then use a compare.

stephentyrone
Posts: 778
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

Re: Coding: Hacks and Snippets

Postby stephentyrone » Mon Apr 27, 2009 8:57 pm UTC

mrkite wrote:On a related note, I was thinking about how much extra work you have to do in an emulator because you don't have C, N, V, or other flags in high level languages. For things like addition, you either have to use a larger operand size than the one you are emulating, or you have to do the addition twice and then use a compare.


Some compilers provide intrinsics for getting at the flags set by integer arithmetic (I know clang/llvm does, at least).
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11052
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Hacks and Snippets

Postby Yakk » Mon Apr 27, 2009 9:36 pm UTC

So you can do a touch faster at the hardware level by throwing even more hardware at it.

Let Adder[n](left, right, carry_in) be an n-bit adder. It has outputs .value (n-bit) and .carry (one bit).

Then
Adder[n](left, right, carry_in).value = Adder[n/2](left[0:n/2], right[0, n/2], carry_in).value + Adder[n/2](left[n/2+1:n], right[n/2+1:n], Adder[n/2](left[0:n/2], right[0, n/2], carry_in).carry) >> n/2
give or take a fencepost bug.

Calculating Adder[n/2](left[0:n/2], right[0, n/2], carry_in).carry, however, takes _time_. So you cheat:
Adder[n](left, right, carry_in).value = Adder[n/2](left[0:n/2], right[0, n/2], carry_in).value + (Adder[n/2](left[0:n/2], right[0, n/2], carry_in).carry?Adder[n/2](left[n/2+1:n], right[n/2+1:n], 1):Adder[n/2](left[n/2+1:n], right[n/2+1:n], 0)) >> n/2
(with the note that 'carry' out is the carry of the selected high-order adder).

Now the high order bits are calculated both ways right from the start. And then you do a switch on which one you trust based on the output of the low order bits.

Using this, you can do addition of n bits of data in O(lg(n)) time instead of the naive O(n) time with O(n) hardware. :)

The downside? More hardware. But not as much as you might think.

Every layer of the 'guess add' increases the amount of hardware needed by 50%.

There are a logarithmic number of guess add layers.

So this increases hardware requirements by a factor of 1.5^(lg n) = e^( ln 1.5 * lg n ) = n^(ln 1.5).

This is a scale on the base O(n) cost, so this works out to be ~ O(n^1.4) space. A 32 bit adder using the above technique ends up taking ~4 times as much space and adds about 6.4 times faster (ignoring overhead). Overhead (you need to drive that carry bit much stronger, layout is much more complex, etc) can eat into that.

Moral of the story: hardware is a weird place to code. :)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 10 guests