New log2_96(x) function - General Discussion and Assistance - CHDK Forum  

New log2_96(x) function

  • 12 Replies
  • 2235 Views
*

Offline lapser

  • *****
  • 1093
New log2_96(x) function
« on: 02 / December / 2012, 12:51:36 »
Advertisements
While writing my new shot_histo code, I developed a new, integer log function specifically for use with CHDK Apex96 exposure values. I think it would be useful to make this function available to Lua and other areas of CHDK. It obviously doesn't belong in shot_histogram.c.

The function will be useful for converting ISO, Shutter Speed, and F-Stop to sv96, tv96, and av96. I'll also include a function that returns an integer value for 2^(x/96), multiplied by a scaling factor for accuracy, to convert the other way.

Will the gurus here take a look at the function and let me know where you think it should go, if you agree that it would be useful? Thanks.
Code: (C) [Select]
int log2_96(unsigned int x)
{
  if(x<2)return 0;
  double dx2=x*1.00361666597546291349; //save x * (2^(1/192) rounding factor
  int x96=-1;
  do //find power of 2 less than x
  {
    x>>=1;
    x96+=1;
  }
  while(x>0);
  double dx1=1U<<x96; //same as 2^x96 -- must use 1U, not 1
  x96 *= 96; // why the function has 96 in the name
 
  while(dx1<dx2) //finds log2 value within 96 times through loop
  {
    dx1 *= 1.00724641222370389809; //2^(1/96)
    x96+=1;
  }
  return x96; 
}

unsigned int pow2_96(int x)
{
  //will add code here
}
« Last Edit: 03 / December / 2012, 00:40:12 by lapser »
EOS-M3_120f / SX50_100b / SX260_101a / G1X_100g / D20_100b
https://www.youtube.com/user/DrLapser/videos

*

Offline lapser

  • *****
  • 1093
Re: New log2_96(x) function
« Reply #1 on: 03 / December / 2012, 01:12:46 »
double dx1=1U<<x96; //same as 2^x96 -- must use 1U, not 1

I discovered a subtle bug in the code that I corrected. I compute 2^x with 1<<x, which works fine until x gets to 31, and the result becomes negative, which produced an infinite loop. To get it to work, the constant "1" has to be unsigned, which you specify as 1U.
EOS-M3_120f / SX50_100b / SX260_101a / G1X_100g / D20_100b
https://www.youtube.com/user/DrLapser/videos

*

Online philmoz

  • *****
  • 3163
    • Photos
Re: New log2_96(x) function
« Reply #2 on: 03 / December / 2012, 03:24:31 »
I did some testing and your function returns values that are off by +1.

E.G. log2_96(2) returns 97 not 96.
Every value I checked was 1 larger than expected.

CHDK already has a log2 function built in so why not use
          (int)(log2(x)*96.0+0.5)

I also timed your code against log2 for values from 1 - 100,000.
    log2_96 averages 41.2 microseconds per call.
    log2 averages 23.2 microseconds per call - almost twice as fast.

The implementation of log2 in the code is done as log10(x)/log10(2) where the value for log10(2) is stored as a constant in the code.

If you want an even faster version use
        (int)(log10(x)*318.9050971+0.5)
where 318.9050971 = 96 / log10(2)

This averages 16.6 microseconds per call.

Phil.
CHDK ports:
  sx30is (1.00c, 1.00h, 1.00l, 1.00n & 1.00p)
  g12 (1.00c, 1.00e, 1.00f & 1.00g)
  sx130is (1.01d & 1.01f)
  ixus310hs (1.00a & 1.01a)
  sx40hs (1.00d, 1.00g & 1.00i)
  g1x (1.00e, 1.00f & 1.00g)
  g5x (1.00c, 1.01a, 1.01b)

*

Offline lapser

  • *****
  • 1093
Re: New log2_96(x) function
« Reply #3 on: 03 / December / 2012, 12:23:15 »
Thanks Phil! You're incredible.

I discovered last night that float and double are done in software, so I'm not surprised at the speed results. Thanks for doing the testing. I bet that most of the time in all the log routines you tested is spent in the floating point emulation code.

The fastest way for log2_96 would be to use a table of 96 pre-calculated values. That would take 384 bytes, or possibly 192 if you could use short. I almost wrote it that way, but I was obsessed with saving memory, not time. I'll use the built in routines you mentioned, and save a little of both.

And exposing a log2_96 function in Lua wouldn't be that helpful. You really want a function that converts TV, SV and AV to their linear values, and vice versa. I wrote one in Lua awhile back using the table technique.
http://chdk.setepontos.com/index.php?topic=8742.msg91368#msg91368

And thanks for discovering the +1 bug. I guess my rounding error fix over-corrected a little.




EOS-M3_120f / SX50_100b / SX260_101a / G1X_100g / D20_100b
https://www.youtube.com/user/DrLapser/videos


*

Offline lapser

  • *****
  • 1093
Re: New log2_96(x) function
« Reply #4 on: 03 / December / 2012, 14:11:35 »
CHDK already has a log2 function built in so why not use
          (int)(log2(x)*96.0+0.5)
I put your equation in my code and it works perfectly. Since I'm actually interested in log2 of the difference between 2 values (pictures), I can get greater accuracy with this:
          (int)((log2(x1)-log2(x2))*96.0+0.5)

x1 is the sum of all the sampled pixels obtained while building a histogram for the current picture. x2 is the same for a previous reference shot. The difference between these two values is the exposure difference between the shots. To match the exposure of the reference shot in the next shot, you would do this (in Lua):

tv=tv+get_shot_ev96rel()

====

I'm assuming you're doing the timing on your computer instead of in the camera. On a related topic, I was trying to time build_shot_histogram() using get_tick_count(). Since the build function is called from a different task, I suspect that the weird bugs I was encountering were due to calling the same routine from different threads. The "bug" I discovered in the new print_screen may have been from this problem.

Do you have a link with information on thread safe programming in CHDK? The section titled communication between tasks says "To Do."

Also, I have an invention I call "the wheel" which I'd like you to look at. I think square is the way to go, don't you?

EOS-M3_120f / SX50_100b / SX260_101a / G1X_100g / D20_100b
https://www.youtube.com/user/DrLapser/videos

*

Offline lapser

  • *****
  • 1093
Re: New log2_96(x) function
« Reply #5 on: 03 / December / 2012, 22:36:31 »
After further testing of the built-in log2 function, I discovered it's not accurate enough for the large values I have. I start out by bit shifting x down to a number between 1 and 2. The log2 function doesn't do that since it's based on log10. If I really wanted to, I could call the log2 function after bit shifting, and get an accurate (double) log value, but I want an integer output value in the end.

So I'm back to using my log2_96  function. I found out why it was always returning +1 and corrected it (I think). For rounding, I was multiplying x by 2^(1/192) instead of dividing. This moved my end point the wrong way. I didn't notice it because I always subtract one value from another, and the errors cancelled out.

So I guess sometimes a square wheel is better?
Code: [Select]
int log2_96(unsigned int x)
{
  if(x<2)return 0;
  double dx2=x*0.99639636716081462905; //save:   x /  2^(1/192) rounding factor
  int x96=-1;
  do //find power of 2 less than x
  {
    x>>=1;
    x96+=1;
  }
  while(x>0);
  double dx1=1U<<x96; //same as 2^x96 -- must use 1U, not 1
  x96 *= 96; // why the function has 96 in the name
  while(dx1<dx2) //finds log2 value within 96 times through loop
  {
    dx1 *= 1.00724641222370389809; //2^(1/96)
    x96+=1;
  }
  return x96; 
}
EOS-M3_120f / SX50_100b / SX260_101a / G1X_100g / D20_100b
https://www.youtube.com/user/DrLapser/videos

*

Online philmoz

  • *****
  • 3163
    • Photos
Re: New log2_96(x) function
« Reply #6 on: 04 / December / 2012, 03:13:28 »
I did all the timing and calculation tests on my G1X.
I added the code into core_spytask (main.c) after the call to shooting_init and before the main loop.
I wrote the results to a file which can be examined with the file browser.

What sort of values for x give inaccurate results from log2?

log2(x1) - log2(x2) = log2((double)x1/(double)x2)

Does this eliminate the accuracy problems? (it will be faster since a floating point divide only takes 5 microseconds instead of the 23 for the second call to log2).

Phil.
CHDK ports:
  sx30is (1.00c, 1.00h, 1.00l, 1.00n & 1.00p)
  g12 (1.00c, 1.00e, 1.00f & 1.00g)
  sx130is (1.01d & 1.01f)
  ixus310hs (1.00a & 1.01a)
  sx40hs (1.00d, 1.00g & 1.00i)
  g1x (1.00e, 1.00f & 1.00g)
  g5x (1.00c, 1.01a, 1.01b)

*

Offline lapser

  • *****
  • 1093
Re: New log2_96(x) function
« Reply #7 on: 04 / December / 2012, 10:11:43 »
I didn't test the 2 functions against each other mathematically. I just noticed that the values from my exposure tests were about 2 less than they should be with log2, and almost perfect with log2_96. The input values I expect are possible are towards the high range of an unsigned int: 2^32. The actual input values from my tests would be around to 2^12 *6000.

I noticed in your post that your decimal constants have 10 digits. I think a double has 15 stable digits, and stops changing at 17 digits. I used 20 digits, figuring the compiler would throw the extras in the bit bucket. You could probably improve the precision of log2 using more digits in the constants. The scientific version of Windows calculator outputs gobs of digits, if you need a new calculator.

The absolute fastest way to do this would be to use a small table. The size of the table is probably less than the size of all the instructions I'm adding! The table would be around 128 bytes. I could allocate it once  and generate it with double multiplications, and then free it, like the histogram buffer. But I bet that would take more than 128 bytes of instructions, so just putting it in the C code as a constant would be best. To make log2_96 a general function for CHDK, this would be the way to go.

Good idea to save a log2 call by dividing. I could probably do the division with a long int even. But I think I read that CHDK doesn't have long int? Is that correct?

That's a clever way to measure timing on the G1X. You run your code before anything else in the camera starts, I assume. The next question is, how did you get the start/stop time values, and can it be done in a function like build_shot_histogram() while the camera is running? I also have the G1X, although probably a different firmware version.

I've attached 2 files with the output of my tests with the different log functions. If you put the both in Notepad++, you can switch tabs and easily see the differences. Ideally, the numbers on the right should all be -32, except for the big jump, which should be 384. -32 is the difference in shutter time between each 2 pictures. The right column is the difference in the logs of the pixel sums in the histogram taken from the raw buffer.
EOS-M3_120f / SX50_100b / SX260_101a / G1X_100g / D20_100b
https://www.youtube.com/user/DrLapser/videos


*

Offline lapser

  • *****
  • 1093
Re: New log2_96(x) function
« Reply #8 on: 04 / December / 2012, 19:36:32 »
I compared the actual numbers from the log2 and log2_96 functions against each other over the whole range of integers, and they were identical. The differences in my tests were from the way I stored the reference value, I think. I'll try again with log2.

So I guess the square wheel ain't so great after all. I'm learning a lot of CHDK and programming from all this, which is the real purpose. Thanks for the help.
EOS-M3_120f / SX50_100b / SX260_101a / G1X_100g / D20_100b
https://www.youtube.com/user/DrLapser/videos

*

Offline lapser

  • *****
  • 1093
Re: New log2_96(x) function
« Reply #9 on: 04 / December / 2012, 20:09:36 »
The implementation of log2 in the code is done as log10(x)/log10(2) where the value for log10(2) is stored as a constant in the code.

If you want an even faster version use
        (int)(log10(x)*318.9050971+0.5)
where 318.9050971 = 96 / log10(2)

This averages 16.6 microseconds per call.
OK, we have a winner. I used this method in the (hopefully) final version... with a few extra digits in the constant to make me feel better. I checkd the output over a wide range of numbers and it was the same as my slower function. Thanks again, Phil.

  int isum=(int)(log10(hsum-bl)*318.9050971091867+0.5); //log2(hsum-bl)*96

hsum is the sum of all the sampled pixel values
bl = (CAM_BLACK_LEVEL)*(total number of pixel samples)
EOS-M3_120f / SX50_100b / SX260_101a / G1X_100g / D20_100b
https://www.youtube.com/user/DrLapser/videos

 

Related Topics