Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (541)
Games in Android Showcase (133)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
   Home   Help   Search   Login   Register   
  Show Posts
Pages: [1]
1  Game Development / Shared Code / Re: Fastest get2fold algorithm on: 2006-04-03 13:12:27
Here is the test harness. I think I have everyone's tweaks in here, but I have commented out the lookup code because of verification errors. If someone can correct this and repost, it would be helpful. I copied the code from the Java 5 Integer.highestOneBit() method so it reduces a method call and also can run in JDK 1.4 VMs.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
202  
203  
204  
205  
206  
207  
208  
209  
210  
211  
212  
213  
214  
215  
216  
217  
218  
219  
220  
221  
222  
223  
224  
225  
226  
227  
228  
229  
230  
231  
232  
233  
234  
235  
236  
237  
238  
239  
240  
241  
242  
243  
244  
245  
246  
247  
248  
249  
250  
251  
252  
253  
254  
255  
256  
257  
258  
259  
260  
261  
262  
263  
264  
265  
266  
267  
268  
269  
270  
271  
272  
273  
274  
275  
276  
277  
278  
279  
280  
281  
282  
283  
284  
285  
286  
287  
288  
289  
290  
291  
292  
293  
294  
295  
296  
297  
298  
299  
300  
301  
302  
303  
304  
305  
306  
307  
308  
309  
310  
311  
312  
313  
314  
315  
316  
317  
318  
319  
320  
321  
322  
323  
324  
325  
326  
327  
328  
329  
330  
331  
332  
333  
334  
335  
336  
337  
338  
339  
340  
341  
342  
343  
344  
345  
346  
347  
348  
349  
350  
351  
352  
353  
354  
355  
356  
357  
358  
359  
360  
361  
362  
363  
364  
365  
366  
367  
368  
369  
370  
371  
372  
public class PowerOfTwo {


   public static final double invln2 = 1.0 / Math.log(2.0);

   /**
    * @author Control
    */

   public static final int get2FoldLog(int num) {
      return (int) Math.pow(2, Math.ceil(Math.log(num) * invln2));
   }

   /**
    * @author Dirk Bosmans Dirk.Bosmans@tijd.com
    * @author Vincent Vollers
    */

   public static final int get2FoldUnrolled(int n) {
      if (n < 0) return 32;
      if (n > 0x00010000) {
         if (n > 0x01000000) {
            if (n > 0x10000000) {
               if (n > 0x40000000) {
                  // if ( n > 0x7fffffff )
                  // return 32
                  // else
                  // return 2147483648; is too much, so return -1
                  return -1;
               } else {
                  // !( n > 0x3fffffff )
                  if (n > 0x20000000) return 1073741824;
                  else return 536870912;
               }
            } else {
               // !( n > 0x0fffffff )
               if (n > 0x04000000) {
                  if (n > 0x08000000) return 268435456;
                  else return 134217728;
               } else {
                  // !( n > 0x03ffffff )
                  if (n > 0x02000000) return 67108864;
                  else return 33554432;
               }
            }
         } else {
            // !( n > 0x00ffffff )
            if (n > 0x00100000) {
               if (n > 0x00400000) {
                  if (n > 0x00800000) return 16777216;
                  else return 8388608;
               } else {
                  // !( n > 0x003fffff )
                  if (n > 0x00200000) return 4194304;
                  else return 2097152;
               }
            } else {
               // !( n > 0x000fffff )
               if (n > 0x00040000) {
                  if (n > 0x00080000) return 1048576;
                  else return 524288;
               } else {
                  // !( n > 0x0003ffff )
                  if (n > 0x00020000) return 262144;
                  else return 131072;
               }
            }
         }
      } else {
         // !( n > 0x0000ffff )
         if (n > 0x00000100) {
            if (n > 0x00001000) {
               if (n > 0x00004000) {
                  if (n > 0x00008000) return 65536;
                  else return 32768;
               } else {
                  // !( n > 0x00003fff )
                  if (n > 0x00002000) return 16384;
                  else return 8192;
               }
            } else {
               // !( n > 0x00000fff )
               if (n > 0x00000400) {
                  if (n > 0x00000800) return 4096;
                  else return 2048;
               } else {
                  // !( n > 0x000003ff )
                  if (n > 0x00000200) return 1024;
                  else return 512;
               }
            }
         } else {
            // !( n > 0x000000ff )
            if (n > 0x00000010) {
               if (n > 0x00000040) {
                  if (n > 0x00000080) return 256;
                  else return 128;
               } else {
                  // !( n > 0x0000003f )
                  if (n > 0x00000020) return 64;
                  else return 32;
               }
            } else {
               // !( n > 0x0000000f )
               if (n > 0x00000004) {
                  if (n > 0x00000008) return 16;
                  else return 8;
               } else {
                  // !( n > 0x00000003 )
                  if (n > 0x00000002) return 4;

                  return n;
               }
            }
         }
      }
   } // end widthInBits

   /**
    * @author James Cook
    */

   public static final int get2FoldShifty(int n) {
      if (n == 0) return 0;
      int power = 0;
      n--;
      while (n > 0) {
         n = n >> 1;
         power++;
      }
      return 1 << power;
   }

   /**
    * @author James Cook
    */

   public static final int get2FoldLogical(int n) {
      int maxPower = 0x40000000;
      while (maxPower > 0) {
         if (n == maxPower) return maxPower;
         if (n > maxPower) return maxPower << 1;
         maxPower = maxPower >> 1;
      }
      return 0;
   }

   /**
    * @author swpalmer
    */

   public static final int p2Bound4(int n) {
      int h1 = n & 0xffff0000;  // 11111111111111110000000000000000
      if (h1 == 0)
         h1 = n & ~0xffff0000;

      int h2 = h1 & 0xff00ff00;  // 11111111000000001111111100000000
      if (h2 == 0)
         h2 = h1 & ~0xff00ff00;

      int h3 = h2 & 0xf0f0f0f0;  // 11110000111100001111000011110000
      if (h3 == 0)
         h3 = h2 & ~0xf0f0f0f0;

      int h4 = h3 & 0xcccccccc;  // 11001100110011001100110011001100
      if (h4 == 0)
         h4 = (h3 & ~0xcccccccc);

      int h5 = h4 & 0xaaaaaaaa;  // 10101010101010101010101010101010
      if (h5 == 0)
         h5 = (h4 & ~0xaaaaaaaa);

      // h5 is the highest set bit in 'n', so we likely need to shift by 1
      return h5 << (h5 - n >>> 31);
   }

   /**
    * @author JDK5 Integer class by way of mabraham ("inlined" the code from Integer)
    */

   private static final int highestOneBit(int n) {
      // already a power-of-2 value
      if ((n & (n - 1)) == 0) return n;
      n |= (n >> 1);
      n |= (n >> 2);
      n |= (n >> 4);
      n |= (n >> 8);
      n |= (n >> 16);
      n = n - (n >>> 1);
      return n << 1;
   }

   public static final int[] lookup = new int[256];

   static {
      for (int i = 0; i < lookup.length; i++)
         lookup[i] = highestOneBit(i);
   }

   public static final int lookup(int val) {
      if (val < 0)
         return -1;
      else if (val < 256)
         return lookup[val];
      else if (val < 65536)
         return lookup[val >> 8] << 8;
      else if (val < 16777216)
         return lookup[val >> 16] << 16;
      else if (val < 2147483647)
         return lookup[val >> 24] << 24;
      return -1;
   }


   /**
    * @author HamsterOfDeath
    */

   public static final int get2FoldFlattened(int n) {
      return n < 0
            ? 0xFFFFFFFF
            : n > 0x00010000
            ? n > 0x01000000
            ? n > 0x10000000
            ? n > 0x40000000
            ? 0xFFFFFFFF
            : (n > 0x20000000) ? 0x40000000 : 0x20000000
            : n > 0x04000000 ? (n > 0x08000000) ? 0x10000000 : 0x08000000 : (n > 0x02000000) ? 0x04000000 : 0x02000000
            : n > 0x00100000
            ? n > 0x00400000
            ? (n > 0x00800000) ? 0x01000000 : 0x00800000
            : (n > 0x00200000) ? 0x00400000 : 0x00200000
            : n > 0x00040000
            ? (n > 0x00080000) ? 0x00100000 : 0x00080000
            : (n > 0x00020000) ? 0x00040000 : 0x00020000
            : n > 0x00000100 ? n > 0x00001000
            ? n > 0x00004000
            ? (n > 0x00008000) ? 0x00010000 : 0x00008000
            : (n > 0x00002000) ? 0x00004000 : 0x00002000
            : n > 0x00000400
            ? (n > 0x00000800) ? 0x00001000 : 0x00000800
            : (n > 0x00000200) ? 0x00000400 : 0x00000200 : n > 0x00000010 ? n > 0x00000040 ?
            (n >
                  0x00000080)
                  ?
                  0x00000100
                  :
                  0x00000080 :
            (n >
                  0x00000020)
                  ?
                  0x00000040
                  :
                  0x00000020 :
            n >
                  0x00000004
                  ?
                  (n >
                        0x00000008)
                        ?
                        0x00000010
                        :
                        0x00000008
                  :
                  (n >
                        0x00000002)
                        ?
                        0x00000004
                        :
                        n;

   }

   public static final int shiftUp(int n) {
      if (n == 0) return 0;
      int result = 1;
      while (result < n) result <<= 1;
      return result;
   }


   public void testPerformance(int run) {
      System.out.println("-- Test run " + run + " with " + NUM + " iterations.");

      long time = System.currentTimeMillis();
      for (int i = 0; i < NUM; i++) get2FoldLog(i);
      time = System.currentTimeMillis() - time;

      System.out.println("Math.log method: " + time);

      time = System.currentTimeMillis();
      for (int i = 0; i < NUM; i++) get2FoldUnrolled(i);
      time = System.currentTimeMillis() - time;

      System.out.println("Rolled out binary search method: " + time);

      time = System.currentTimeMillis();
      for (int i = 0; i < NUM; i++) get2FoldShifty(i);
      time = System.currentTimeMillis() - time;

      System.out.println("Shifty method: " + time);

      time = System.currentTimeMillis();
      for (int i = 0; i < NUM; i++) get2FoldLogical(i);
      time = System.currentTimeMillis() - time;

      System.out.println("Logical method: " + time);

      time = System.currentTimeMillis();
      for (int i = 0; i < NUM; i++) p2Bound4(i);
      time = System.currentTimeMillis() - time;

      System.out.println("p2Bound4 method: " + time);

      time = System.currentTimeMillis();
      for (int i = 0; i < NUM; i++) highestOneBit(i);
      time = System.currentTimeMillis() - time;

      System.out.println("highestOneBit method: " + time);

//      time = System.currentTimeMillis();
//      for (int i = 0; i < NUM; i++) lookup(i);
//      time = System.currentTimeMillis() - time;
//
//      System.out.println("lookup method: " + time);

      time = System.currentTimeMillis();
      for (int i = 0; i < NUM; i++) get2FoldFlattened(i);
      time = System.currentTimeMillis() - time;

      System.out.println("get2FoldFlattened method: " + time);

      time = System.currentTimeMillis();
      for (int i = 0; i < NUM; i++) shiftUp(i);
      time = System.currentTimeMillis() - time;

      System.out.println("shiftUp method: " + time);
   }

   public void testAccuracy() {
      System.out.println("-- Accuracy run ");

      for (int i = 1; i < 0x4000000; i++) {
         int i1 = get2FoldLog(i);
         int i2 = get2FoldUnrolled(i);
         int i3 = get2FoldShifty(i);
         int i4 = get2FoldLogical(i);
         int i5 = p2Bound4(i);
         int i6 = highestOneBit(i);
         int i7 = get2FoldFlattened(i);
         int i8 = shiftUp(i);

         if (i1 != i2 || i2 != i3 || i3 != i4 ||
               i4 != i5 || i5 != i6 || i6 != i7 || i7 != i8) {
            System.err.println("Error in results for i = " + i +
                  ", Log:" + i1 + ", Unrolled: " + i2 +
                  ", Shifty: " + i3 + ", Logical: " + i4 +
                  ", p2Bound4: " + i5 + ", highestOneBit: " + i6 +
                  ", get2FoldFlattened: " + i7 + ", shiftUp: " + i8);
            System.err.println("Stopping test. (there may be other inaccuracies.)");
            System.exit(-1);
         }
      }
      System.out.println("All methods return the exact same results.");
   }

   public PowerOfTwo() {
      testAccuracy();
      for (int i = 0; i < 5; i++) {
         testPerformance(i + 1);
      }
   }

   public static int NUM = 5000000;

   public static void main(String[] args) {
      new PowerOfTwo();
   }
}
2  Game Development / Shared Code / Re: Fastest get2fold algorithm on: 2006-04-03 13:10:00
On my machine, some of the more optimized solutions are clocking in at less than 100 ms for 5,000,000 iterations. Any of the algorithms presented thus far are suitable replacements for the java.lang.Math approach, but it is fun to see the different approaches to the problem. In the back of your mind, you begin to feel that there is an extremely elegant and simple solution to this problem, and the highestOneBit algorithm probably comes closest.

For the sake of summary, I have collected all of the algorithms mentioned so far into a single test harness that verifies their accuracy and performs a micro-benchmark. As swpalmer noted, the lookup code produces inaccurate results. This may be caused by my initialization of the lookup table.

Since this is a micro-benchmark, take it with a grain of salt. I would expect some algorithms to be faster than others and vice-versa when run on different OS, processor, ot Java VM. (Actually, I wouldn't expect this, but it turns out that way. Maybe it is just the VM that makes all of the difference.)

Here are the results of my tests:

Windows P4 2.8GHz
java version "1.4.2_10"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2_10-b03)
Java HotSpot(TM) Client VM (build 1.4.2_10-b03, mixed mode)


1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
>java -cp . PowerOfTwo
-- Accuracy run
All methods return the exact same results.
-- Test runs with 5000000 iterations.
Math.log method: 6219, 6453, 6453, 6469, 6453
Rolled out binary search method: 94, 94, 93, 93, 94
Shifty method: 281, 313, 313, 313, 312
Logical method: 156, 156, 156, 141, 141
p2Bound4 method: 141, 140, 156, 141, 141
highestOneBit method: 156, 141, 141, 125, 140
get2FoldFlattened method: 93, 94, 94, 94, 94
shiftUp method: 235, 250, 250, 234, 250


The 1.4 VM shows the Math.log code more than a magnitude slower than some of the optimized routines, as one might expect. The BS approach, that started this thread, by Dirk Bosmans and Vincent Vollers still performs the best in this configuration. The approaches that use some type of bit-shifting are close behind.


Windows P4 2.8GHz
java version "1.4.2_10"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2_10-b03)
Java HotSpot(TM) Server VM (build 1.4.2_10-b03, mixed mode)


1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
>java -cp . -server PowerOfTwo
-- Accuracy run
All methods return the exact same results.
-- Test runs with 5000000 iterations.
Math.log method: 2953, 2891, 2953m 2907, 2922
Rolled out binary search method: 79, 78, 78, 78, 63
Shifty method: 250, 266, 265, 265, 265
Logical method: 156, 140, 141, 157, 141
p2Bound4 method: 78, 78, 78, 62, 78
highestOneBit method: 78, 78, 78, 94, 78
get2FoldFlattened method: 78, 79, 78, 62, 78
shiftUp method: 210, 210, 211, 210, 210


I took a moment to run the VM in server mode. I wasn't expecting to see much change since we are only performing such minimal computations. I was wrong. Perhaps there is much more aggressive inlining occurring? I'm not sure, but all of the benchmarks were reduced, and significantly in the case of the java.lang.Math functions. Also, the p2Bound4 and highestOneBit algorithms now match the performance of the BS approaches.


Windows P4 2.8GHz
java version "1.6.0-beta"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.6.0-beta-b59g)
Java HotSpot(TM) Client VM (build 1.6.0-beta-b59g, mixed mode, sharing)


1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
>java -cp . PowerOfTwo
-- Accuracy run
All methods return the exact same results.
-- Test runs with 5000000 iterations.
Math.log method: 4329, 4328, 4375, 4390, 4391
Rolled out binary search method: 78, 78, 78, 63, 78
Shifty method: 218, 219, 234, 219, 219
Logical method: 172, 172, 172, 172, 156
p2Bound4 method: 78, 78, 78, 78, 78
highestOneBit method: 79, 78, 79, 78, 78
get2FoldFlattened method: 78, 78, 78, 78, 78
shiftUp method: 220, 215, 214, 214, 210


Running the benchmarks under the Java 6 beta produced similar results as the server mode results above, but with not so great a performance bump for the java.lang.Math routine. There is no server VM for my beta JDK download, so that test is not included.

IBM p590 Server
java version "1.4.2"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2)
Classic VM (build 1.4.2, J2RE 1.4.2 IBM AIX build ca142ifx-20050119 SR1+80507+81622 (JIT enabled: jitc))



1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
> /usr/java14/bin/java -cp . PowerOfTwo
-- Accuracy run
All methods return the exact same results.
-- Test runs with 5000000 iterations.
Math.log method: 1271, 1269, 1240, 1212, 1208
Rolled out binary search method: 98, 96, 97, 96, 96
Shifty method: 0, 0, 0, 0, 0
Logical method: 325, 321, 324, 327, 324
p2Bound4 method: 87, 85, 87, 86, 86
highestOneBit method: 0, 0, 0, 0, 0
get2FoldFlattened method: 112, 110, 110, 110, 111
shiftUp method: 0, 0, 0, 0, 0


This is the test result for my production server environment. This hardware accelerates the simple bit-shifting algorithms (with minimal looping) to the point that I couldn't measure them. Shifty, highestOneBit, and ShiftUp executed 5MM iterations in less than 10 ms! That's quite a bit of optimization. The same hardware produced some of the lowest scores for the BS routines.
3  Game Development / Shared Code / Re: Fastest get2fold algorithm on: 2006-03-20 23:32:32
Sorry to repeat this code block here. I added a couple other methods that use bit shifting. All results are certified accurate up to 0x4000000.

More performance is possible by doing a bottom-up search for a power of two instead of the top-down that I used. It might even prove much faster if the starting point was chosen using a few if clauses, As it is, I start with the max power of two and shift down until I am lower than the target number.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
202  
203  
204  
205  
public class PowerOfTwo {


   public static final double invln2 = 1.0 / Math.log(2.0);

   public static int get2FoldLog(int num) {
      return (int) Math.pow(2, Math.ceil(Math.log(num) * invln2));
   }

   /**
    * Calculate how many bits wide a number is,
    * i.e. position of highest 1 bit.
    * Fully unraveled binary search method.
    *
    * @return p where 2**p is first power of two >= n.
    *         e.g. binary 0001_0101 -> 5, 0xffffffff -> 32,
    *         0 -> 0, 1 -> 1, 2 -> 2, 3 -> 2, 4 -> 3
    *         <p/>
    *         (Vincent) Changed to return 2^n instead of n
    * @author Dirk Bosmans Dirk.Bosmans@tijd.com
    * @author Vincent Vollers
    */

   public static final int get2FoldUnrolled(int n) {
      if (n < 0) return 32;
      if (n > 0x00010000) {
         if (n > 0x01000000) {
            if (n > 0x10000000) {
               if (n > 0x40000000) {
                  // if ( n > 0x7fffffff )
                  // return 32
                  // else
                  // return 2147483648; is too much, so return -1
                  return -1;
               } else {
                  // !( n > 0x3fffffff )
                  if (n > 0x20000000) return 1073741824;
                  else return 536870912;
               }
            } else {
               // !( n > 0x0fffffff )
               if (n > 0x04000000) {
                  if (n > 0x08000000) return 268435456;
                  else return 134217728;
               } else {
                  // !( n > 0x03ffffff )
                  if (n > 0x02000000) return 67108864;
                  else return 33554432;
               }
            }
         } else {
            // !( n > 0x00ffffff )
            if (n > 0x00100000) {
               if (n > 0x00400000) {
                  if (n > 0x00800000) return 16777216;
                  else return 8388608;
               } else {
                  // !( n > 0x003fffff )
                  if (n > 0x00200000) return 4194304;
                  else return 2097152;
               }
            } else {
               // !( n > 0x000fffff )
               if (n > 0x00040000) {
                  if (n > 0x00080000) return 1048576;
                  else return 524288;
               } else {
                  // !( n > 0x0003ffff )
                  if (n > 0x00020000) return 262144;
                  else return 131072;
               }
            }
         }
      } else {
         // !( n > 0x0000ffff )
         if (n > 0x00000100) {
            if (n > 0x00001000) {
               if (n > 0x00004000) {
                  if (n > 0x00008000) return 65536;
                  else return 32768;
               } else {
                  // !( n > 0x00003fff )
                  if (n > 0x00002000) return 16384;
                  else return 8192;
               }
            } else {
               // !( n > 0x00000fff )
               if (n > 0x00000400) {
                  if (n > 0x00000800) return 4096;
                  else return 2048;
               } else {
                  // !( n > 0x000003ff )
                  if (n > 0x00000200) return 1024;
                  else return 512;
               }
            }
         } else {
            // !( n > 0x000000ff )
            if (n > 0x00000010) {
               if (n > 0x00000040) {
                  if (n > 0x00000080) return 256;
                  else return 128;
               } else {
                  // !( n > 0x0000003f )
                  if (n > 0x00000020) return 64;
                  else return 32;
               }
            } else {
               // !( n > 0x0000000f )
               if (n > 0x00000004) {
                  if (n > 0x00000008) return 16;
                  else return 8;
               } else {
                  // !( n > 0x00000003 )
                  if (n > 0x00000002) return 4;

                  return n;
               }
            }
         }
      }
   } // end widthInBits


   public static final int get2FoldShifty(int n) {
      if (n == 0) return 0;
      int power = 0;
      n--;
      while (n > 0) {
         n = n >> 1;
         power++;
      }
      return 1 << power;
   }

   public static final int get2FoldLogical(int n) {
      int maxPower = 0x40000000;
      while (maxPower > 0) {
         if (n == maxPower) return maxPower;
         if (n > maxPower) return maxPower << 1;
         maxPower = maxPower >> 1;
      }
      return 0;
   }


   public void testPerformance(int run) {
      System.out.println("-- Test run " + run);

      long time = System.currentTimeMillis();
      for (int i = 0; i < NUM; i++) get2FoldLog(i);
      time = System.currentTimeMillis() - time;

      System.out.println("Math.log method: " + time);

      time = System.currentTimeMillis();
      for (int i = 0; i < NUM; i++) get2FoldUnrolled(i);
      time = System.currentTimeMillis() - time;

      System.out.println("Rolled out binary search method: " + time);

      time = System.currentTimeMillis();
      for (int i = 0; i < NUM; i++) get2FoldShifty(i);
      time = System.currentTimeMillis() - time;

      System.out.println("Shifty method: " + time);

      time = System.currentTimeMillis();
      for (int i = 0; i < NUM; i++) get2FoldLogical(i);
      time = System.currentTimeMillis() - time;

      System.out.println("Logical method: " + time);
   }

   public void testAccuracy() {
      System.out.println("-- Accuracy run ");

      for (int i = 0; i < 0x4000000; i++) {
         int i1 = get2FoldLog(i);
         int i2 = get2FoldUnrolled(i);
         int i3 = get2FoldShifty(i);
         int i4 = get2FoldLogical(i);
         if (i1 != i2 || i2 != i3 || i3 != i4) {
            System.err.println("Error in results: " + i +
                  " Log:" + i1 + ", Unrolled: " + i2 +
                  ", Shifty: " + i3 + ", Logical: " + i4);
            System.err.println("Stopping test, there may be other inaccuracies.");
            return;
         }
      }
      System.out.println("All methods return the exact same results.");
   }

   public PowerOfTwo() {
      for (int i = 0; i < 5; i++) {
         testPerformance(i + 1);
      }
      testAccuracy();
   }

   public static int NUM = 1000000;

   public static void main(String[] args) {
      new PowerOfTwo();
   }
}
4  Java Game APIs & Engines / JOGL Development / Re: How to: Getting started with JOGL on: 2006-01-15 18:07:01
May you update the tutorial to the jogl jsr-231 standard?
Thanks!

I've used JOGL for about an hour, and I have no experience with OpenGL  so some of the changes I made may be totally screwy. Please take them with a grain of salt, or better yet, post an improvement. I've attempted to bring Gregory Pierce's original example up to date with the JSR-231 release of JOGL as Pegasus requested.

Gregory  (back in July 2003) used a factory to get the GLCanvas. I am using the latest release (JSR-231 beta 02 build) and these methods no longer exist. In addition, the demos that are distributed with this release use a simple default constructor call to instantiate a GLCanvas object. So I did that also.

The original code also stored the GL object in an instance variable. According to the JOGL User's Guide this isn't recommended because of potential threading conflicts. I realize that the initial code example won't have any multithreading issues, but it is a simple change that may help noobies use best practices from the start. Here's the snippet from the user's guide:

Quote
It is strongly recommended that applications always refetch the GL object out of the GLAutoDrawable upon each call to the init(), display() and reshape() methods and pass the GL object down on the stack to any drawing routines, as opposed to storing the GL in a field and referencing it from there. The reason is that multithreading issues inherent to the AWT toolkit make it difficult to reason about which threads certain operations are occurring on, and if the GL object is stored in a field it is unfortunately too easy to accidentally make OpenGL calls from a thread that does not have a current context. This will usually cause the application to crash.

Here is the revised code. Copy it into a file named Trangle.java.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
import java.awt.*;
import java.awt.event.*;
import java.util.logging.*;
import javax.media.opengl.*;

import com.sun.opengl.utils.Animator;

public class Triangle implements GLEventListener {

   // Statics -----------------------------------------------------------------

   private final Logger LOG = Logger.getLogger(Triangle.class.getName());

   public static void main(String[] args) {
      Frame frame = new Frame("Triangle Demo");

      GLCanvas canvas = new GLCanvas();
      canvas.addGLEventListener(new Triangle());

      frame.add(canvas);
      frame.setSize(512, 512);

      final Animator animator = new Animator(canvas);
      frame.addWindowListener(new WindowAdapter() {
         public void windowClosing(WindowEvent e) {
            new Thread(new Runnable() {
               public void run() {
                  animator.stop();
                  System.exit(0);
               }
            }).start();
         }
      });
      frame.setVisible(true);
      animator.start();
   }

   // Constructors ------------------------------------------------------------

   public Triangle() {
   }

   // GLEventListener ---------------------------------------------------------

   public void init(GLAutoDrawable drawable) {
      GL gl = drawable.getGL();
      if (LOG.isLoggable(Level.FINE))
         LOG.fine("Init GL is " + gl.getClass().getName());
   }

   public void display(GLAutoDrawable drawable) {
      GL gl = drawable.getGL();
      gl.glClear(GL.GL_COLOR_BUFFER_BIT | GL.GL_DEPTH_BUFFER_BIT);
      gl.glLoadIdentity();
      gl.glColor3f(1F, 0F, 0F);

      gl.glBegin(GL.GL_TRIANGLES);

      gl.glVertex3f(0.0F, 0.0F, 0.0F);
      gl.glVertex3f(1.0F, 0.0F, 0.0F);
      gl.glVertex3f(1.0F, 1.0F, 0.0F);

      gl.glEnd();
   }

   public void reshape(GLAutoDrawable drawable, int i, int i1, int i2, int i3) {
   }

   public void displayChanged(GLAutoDrawable drawable, boolean b, boolean b1) {
   }
}


Some people were experiencing difficulties getting the code compiled or running. I downloaded the latest version of JOGL which was JSR-231 beta 02 build at the time I wrote this. Download jogj.jar to your local system.

Also, download the native library that is specific to your runtime environment. I'm using Windows, so I downloaded jogl-natives-win32.jar. This jar file contains DLL's that the Java Runtime environment must be able to load. I'm not sure why they are distributed as a jar file since that typically implies that the archive should remain compressed, however in our case, we want to expand the DLLs from within this archive. As far as I know, Java cannot load library files (DLLs in this case) from inside an archive. Use Java's jar utility to expand the contents of the native archive into a directory somewhere. You can also use any tool that can extract files from a ZIP archive. I ended up extracting 3 DLL files from the archive and put them in a local directory.

At this point, you have the jogl.jar (mine is in c:\jogl) and some native files in a directory (mine are in c:\jogl\native). You also should have the source code example in a file called Triangle.java (mine is in c:\jogl\examples\Triangle.java). To compile the source code from the command line (again in Windows). I'm in the c:\jogl\examples directory when I execute this:
1  
javac -classpath c:\jogl\jogl.jar Triangle.java


When the compile finishes, there are 3 class files in the directory now. The main class is Triangle.class, and the other two classes are inner classes. If you followed Gregory Pierce's original suggestion and placed you native files in your Java environment's extension directory you can simply run the application using the following:
1  
java -classpath c:\jogl\jogl.jar ;. Triangle


Usually, three things happen at this point. The app runs, hurrah. Or, the app fails with a "Exception in thread "main" java.lang.NoClassDefFoundError: Triangle" message. Or the application fails with a "Exception in thread "main" java.lang.UnsatisfiedLinkError: no jogl in java.library.path" error.

If the app ran fine the first time, congratulations. You have caught up with me and we are both about to wade waist deep into the exciting and sometimes scary world of 3D development.

If you received the "Exception in thread "main" java.lang.NoClassDefFoundError: Triangle" error, fear not. You probably didn't notice the ";." I added on to the classpath attribute. In order for the Java runtime to discover the Triangle.class file, we have to add the directory this file resides in to the classpath. On Linux and Mac machines, the directories on the classpath are separated with a colon ":" instead of a semi-colon ";".

If you received the "Exception in thread "main" java.lang.UnsatisfiedLinkError: no jogl in java.library.path" error, it indicates that the Java runtime was not able to find the native files that JOGL required. It also means that you didn't copy these files into your Java environment's extension directory. I don't usually do that either. I like to explicitly reference native libraries instead of the system finding them by magic. It especially helps to be explicit when you have multiple versions of native libraries in use like you might as the JOGL libraries evolve over time.

The Java runtime looks for the native files in the directories specified by the system property named "java.libary.path". This system library path can be set in many ways, but the easiest is on the command line as you execute the program:
1  
\java -Djava.library.path=c:\jogl\native -classpath c:\jogl\jogl.jar ;. Triangle


I've uploaded an example of what you should see on your screen when this runs successfully. If you are as green as I am, the next thing to learn is why is the triangle positioned there? Why do we see it from this direction? How do we rotate a viewpoint around the camera. I've got so much to learn! Be sure to download the demos and their source. I feel that this will be an invaluable resource.

Other starting points that I am about to read are:
The OpenGL Redbook
Some intro code snippets at NeonHelium
and these forums, of course.


Jim Cook
Pages: [1]
 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Mr.CodeIt (24 views)
2014-12-23 03:34:11

rwatson462 (55 views)
2014-12-15 09:26:44

Mr.CodeIt (45 views)
2014-12-14 19:50:38

BurntPizza (89 views)
2014-12-09 22:41:13

BurntPizza (112 views)
2014-12-08 04:46:31

JscottyBieshaar (83 views)
2014-12-05 12:39:02

SHC (92 views)
2014-12-03 16:27:13

CopyableCougar4 (100 views)
2014-11-29 21:32:03

toopeicgaming1999 (160 views)
2014-11-26 15:22:04

toopeicgaming1999 (159 views)
2014-11-26 15:20:36
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!