Difference between revisions of "Hex"

From Second Life Wiki
Jump to navigation Jump to search
(report the Efficiency Tester llGetTime results that show cleverness to be fast is too negligible to measure reliably, not yet the Code Racer results that show a measurable good)
m (<lsl> tag to <source>)
 
(3 intermediate revisions by 2 users not shown)
Line 15: Line 15:
|}
|}


Note: Results with eight nybbles begin always with one of the positive signed nybbles 1 2 3 4 5 6 7, never with a zero or unsigned nybble 0 8 9 A B C D E F, except for the boundary test case of the most negative integer "-0x80000000".
Note: Always begins any result of eight nybbles with one of the positive signed nybbles 1 2 3 4 5 6 7, never with a zero or unsigned nybble 0 8 9 A B C D E F, except for the boundary test case of the most negative integer "-0x80000000".
 
Caution: This page has been a work in progress since 2007-10. The specification, implementations, data, and analysis may not yet be totally consistent. See the [[Talk:Hex|discussion]] tab.
</div>
</div>
</div>
</div>
Line 23: Line 21:
<div id="box">
<div id="box">


== Implementations ==
== Code ==
<div style="padding: 0.5em;">
<div style="padding: 0.5em;">


Here you find three kinds of code that implement the one specification. The concise & conventional code details and implements the specification. The clever & small code reduces the code size reported by llGetFreeMemory. The clever & fast code reduces the run time reported by llGetTime when called to calculate the hex for 0x7fffFFFF.
The brief, clear, conventional code here implements this specification exactly.
 
To discover what code ran fastest, we ran the [[Code Racer]] harness. To quote the run time cost as a range of milliseconds, we ran the [[Efficiency Tester]] harness 1,000 times. Measuring run time accurately requires time & attention: for instance, running thru 200ms for 1,000 times necessarily takes at least 200s, ''aka'', more than 3 minutes.
 
To see the raw data and arithmetic that stand behind the summary results briefly presented here, visit the [[Talk:Hex|discussion]] tab.
 
=== Concise & Conventional ===
 
You should choose this code when you care more about concise & conventional than about small & fast.


You should feel that this concise & conventional code is easy to review and modify. For example, you should immediately understand the comment that tells you how to substitute the easy-to-read upper case A B C D E F nybbles of IBM style for the easy-to-type lower case a b c d e f nybbles of AT&T style. Also you should immediately see what results to expect this code to return for any input.
The [[Efficient Hex]] article presents an alternative approach: clever, small, and fast code to implement the same specification and related specifications, and also links to instruments that measure small and fast.


<pre>
<source lang="lsl2">
// http://wiki.secondlife.com/wiki/hex
// http://wiki.secondlife.com/wiki/hex


Line 72: Line 62:
     }
     }
}
}
</pre>
</source>


347 bytes of code reported by llGetFreeMemory -- more than the small code and more than the fast code
</div>
</div>


29+-1 milliseconds of run time reported by llGetTime -- more than the small code and more than the fast code
<div id="box">


=== Clever & Small ===
== Demo Results ==
<div style="padding: 0.5em;">


You should choose this code when you care more about small & fast & clever than about concise & conventional.
Running the demo should produce exactly these results:
 
We wrote this clever & small code to show how to reduce the code size reported by [[llGetFreeMemory]]. We think this code produces the same results as the concise & conventional code. After adequate education & review, you should agree.


<pre>
<pre>
// http://wiki.secondlife.com/wiki/hex
Hello
 
0x0 == 0
string hex(integer value)
0x400 == (0x00FEDC00 & -0x00FEDC00)
{
0x40000000 == (1 << 30)
    string lead = "0x";
-0x80000000 == 0x80000000
    if (value & 0x80000000) // means (integer < 0) but is smaller and faster
-0x123678a == 0xFEDC9876
    {
-0x1 == -1
        lead = "-0x";
-0x1 == 0x123456789
        value = -value; // unnecessary when value == -0x80000000
OK
    }
Hello again
 
0x7fffffff as base
    string nybbles = "";
0x7fffffff by owner
    do
0x0 by group
    {
0x0 by anyone
        integer lsn = value & 0xF; // least significant nybble
0x82000 by next owner
        nybbles = llGetSubString("0123456789abcdef", lsn, lsn) + nybbles;
aka 532480
    } while ((value = (0xfffFFFF & (value >> 4))));
OK
 
    return lead + nybbles;
}
</pre>
</pre>
197 bytes of code reported by llGetFreeMemory -- less than the concise & conventional code and less than the fast code
26+-1 milliseconds of run time reported by llGetTime -- measurably less than the concise & conventional code, and more than the fast code when raced
=== Clever & Fast ===
You should choose this code when you care more about fast & small & clever than about concise & conventional.
We wrote this clever & fast code to show how to reduce the run time reported by [[llGetTime]]. We think this code produces the same results as the concise & conventional code. After adequate education & review, you should agree.
This code cleverly packs all the source lines into one function, not two. This code cleverly assigns a variable and passes a copy of that variable within the parameter list of a function call, which works only when you & the compiler agree over which parameters to evaluate first. This code cleverly loops once per nonzero nybble, rather than unrolling the loop. This code cleverly zeroes the most significant nybble once per loop, rather than zeroing that nybble once and then looping separately to process the remaining nybbles if any. This code cleverly declares its variables outside the loop. All these many clever implementation choices produce real differences in run time that [[llGetTime]] can quickly measure for you thru a test harness like [[Code Racer]].
<pre>
string hex(integer value)
{
    string lead = "0x";
    if (value & 0x80000000) // means (integer < 0) but is smaller and faster
    {
        lead = "-0x";
        value = -value; // unnecessary when value == -0x80000000
    }
    integer lsn; // least significant nybble
    string nybbles = "";
    do
    {
        nybbles = llGetSubString("0123456789abcdef", lsn = (value & 0xF), lsn) + nybbles;
    }
    while ((value = (0xfffFFFF & (value >> 4))));
   
    return lead + nybbles;
}
</pre>
202 bytes of code reported by llGetFreeMemory - less than concise & conventional code, but more than the small code
27+-1 milliseconds of run time reported by llGetTime - less than the concise & conventional code and less than the small code when raced


</div>
</div>
Line 149: Line 98:


<div id="box">
<div id="box">
== Analysis ==


<div style="padding: 0.5em">
== Demo ==
<div style="padding: 0.5em;">


=== Demo ===
To reproduce exactly the expected demo results above, run the demo code below.


Run this demo code to confirm that you get exactly the expected demo results below. We chose test cases that astonish people new to hex.
We chose test cases that astonish people new to hex and test cases that astonish people new to LSL permission masks.


We also chose test cases that astonish people new to LSL permission masks. You'll get the permission mask results we show if you create a New Script to run this demo in. If instead you tried modifying some old script to run this demo, then you might have to edit its permission masks to get the demo results that we show here.
You'll get the permission mask results we show if you create a New Script to run this demo in. If instead you try modifying some old script to run this demo, then you might have to edit its permission masks to get the demo results that we show here.


<pre>
<source lang="lsl2">
default
default
{
{
Line 185: Line 134:
     }
     }
}
}
</pre>
</source>


=== Demo Results ===
</div>
</div>


Running the demo above to call your choice of code should produce exactly these results:
<div id="box">


<pre>
== Specification ==
Hello
<div style="padding: 0.5em;">
0x0 == 0
0x400 == (0x00FEDC00 & -0x00FEDC00)
0x40000000 == (1 << 30)
-0x80000000 == 0x80000000
-0x123678a == 0xFEDC9876
-0x1 == -1
-0x1 == 0x123456789
OK
Hello again
0x7fffffff as base
0x7fffffff by owner
0x0 by group
0x0 by anyone
0x82000 by next owner
aka 532480
OK
</pre>
 
=== Measuring Concise & Conventional & Small & Fast ===
 
Measuring concise  & conventional is hard. Computer programmers often disagree, like other poets. Possibly the most useful opinions come from the http://www.jargon.net/jargonfile/l/languagelawyer.html community.


Measuring small is easy. Compile two copies of the code into one script, call llGetFreeMemory, delete one copy, and report the difference. For more detailed instructions, especially if your results are off by exactly four bytes, see the [[Code Sizer]] article.
We chose requirements that astonish people who usually write clever, small, or fast code by taking as precedent a specification from the far off world of people who usually write brief, clear, and conventional code.


Measuring fast is tedious. Choosing representative test cases is more art than science, then the [[Code Racer]] harness tells us quickly what code runs fastest, then the [[Efficiency Tester]] quotes run time as a range of milliseconds for us.
We require exactly the same results as the hex function of the popular Python scripting language. We thus reproduce how hex integer literals often appear in LSL script, conforming to such arbitrary and traditional AT&T C conventions as:
 
=== Specification Design Rationale ===
 
The specification requires exactly the same results as the hex function of the Python scripting language.
 
The specification reproduces how hex integer literals often appear in LSL script, conforming to such arbitrary and traditional AT&T C conventions as:


# return lower case a b c d e f rather than upper case A B C D E F,
# return lower case a b c d e f rather than upper case A B C D E F,
# return a signed 31-bit result if negative, rather than an unsigned 32-bit result,
# return a signed 31-bit result if negative, rather than an unsigned 32-bit result,
# omit the leading quads of zeroed bits, except returns "0x0" rather than "0x" when the result is zero,
# omit the leading zeroed nybbles, except return "0x0" rather than "0x" when the result is zero,
# return a meaningless "0" before the "x",  as LSL and C compilers require,
# return a meaningless "0" before the "x",  as LSL and C compilers require,
# return the "x" on the left as in LSL and C, not the "h" on the right as in Assembly code, and
# return the "x" on the left as in LSL and C, not the "h" on the right as in Assembly code, and
Line 235: Line 158:


Disputes over the detailed specification of the Python hex function appear buried deep within http://www.python.org/dev/peps/pep-0237/
Disputes over the detailed specification of the Python hex function appear buried deep within http://www.python.org/dev/peps/pep-0237/
As you read this page, you have to wade thru more than one implementation because our LSL wiki serves more than one community of LSL authors. New authors need to see concise & conventional exemplars first, experts find appropriate uses for the clever & small & fast exemplars.
We don't know how to write LSL that implements a hex function that is concise and conventional and small and fast, all at once. We think that design goal is an impossibility in LSL, as in many other programming languages.
=== Different & Concise & Small ===
When you can accept the cost of abandoning the conventional specification, you can make the code still more concise and smaller and faster.
This code sees the most significant bit of the integer as just another data bit, rather than as the sign bit, so results with eight nybbles can begin with any of the nonzero unsigned nybbles 1 2 3 4 5 6 7 8 9 A B C D E F. This code also doesn't bother to calculate the "-0x" or "0x" part of the conventional answer.
This code returns "0" for 0, unsigned "80000000" for -0x80000000, "FFFFFFFF" for -0x1, etc. The code presented here does return easy-to-read upper case A B C D E F nybbles, but exactly the same small size of code can return easy-to-type lower case a b c d e f nybbles.
Note: Reworking this concise & small code into the clever & fast style does make this different code larger and faster, producing 161 bytes of code that runs faster when raced.
<pre>
// http://wiki.secondlife.com/wiki/hex
string bits2nybbles(integer bits)
{
    string nybbles = "";
    do
    {
        integer lsn = bits & 0xF; // least significant nybble
        nybbles = llGetSubString("0123456789ABCDEF", lsn, lsn) + nybbles;
    } while (bits = (0xfffFFFF & (bits >> 4)));
    return nybbles;
}
</pre>
139 bytes of code reported by llGetFreeMemory, less than all the other code
26+-1 milliseconds of run time reported by llGetTime, less than the clever & fast code when raced


</div>
</div>
Line 275: Line 165:


== See Also ==
== See Also ==
<div style="padding: 0.5em">
<div style="padding: 0.5em;">
 
'''Articles'''
* [[Efficient Hex]]


'''Functions'''
'''Functions'''
Line 281: Line 174:
* [[llGetObjectPermMask]]
* [[llGetObjectPermMask]]
* [[llIntegerToBase64]]
* [[llIntegerToBase64]]
* [[llBase64ToInteger]]
* [[llGetFreeMemory]]
* [[llGetTime]]
* [[llMessageLinked]]
* [[llList2Integer]]
* [[llList2String]]


'''Wikipedia'''
'''Wikipedia'''
* http://en.wikipedia.org/wiki/Exemplar
* {{Wikipedia|Exemplar}}
* http://en.wikipedia.org/wiki/Optimization_(computer_science)#When_to_optimize
* {{Wikipedia|Principle_of_least_astonishment}}
* http://en.wikipedia.org/wiki/Principle_of_least_astonishment


</div>
</div>

Latest revision as of 14:14, 24 January 2015

Function: string hex(integer value);

Returns the hexadecimal nybbles of the signed integer value in order. Specifically returns the nybbles from most to least significant, starting with the first nonzero nybble, folding every nybble to lower case, and beginning with the nonnegative prefix "0x" or the negative prefix "-0x".

Parameters:

• integer value – signed value to be expressed as negative or nonnegative hex

Note: Always begins any result of eight nybbles with one of the positive signed nybbles 1 2 3 4 5 6 7, never with a zero or unsigned nybble 0 8 9 A B C D E F, except for the boundary test case of the most negative integer "-0x80000000".

Code

The brief, clear, conventional code here implements this specification exactly.

The Efficient Hex article presents an alternative approach: clever, small, and fast code to implement the same specification and related specifications, and also links to instruments that measure small and fast. 

// http://wiki.secondlife.com/wiki/hex

string XDIGITS = "0123456789abcdef"; // could be "0123456789ABCDEF"

string hexes(integer bits)
{
    string nybbles = "";
    while (bits)
    {
        integer lsn = bits & 0xF; // least significant nybble
        string nybble = llGetSubString(XDIGITS, lsn, lsn);
        nybbles = nybble + nybbles;
        bits = bits >> 4; // discard the least significant bits at right
        bits = bits & 0xfffFFFF; // discard the sign bits at left
    }
    return nybbles;
}

string hex(integer value)
{
    if (value < 0)
    {
        return "-0x" + hexes(-value);
    }
    else if (value == 0)
    {
        return "0x0"; // hexes(value) == "" when (value == 0)
    }
    else // if (0 < value)
    {
        return "0x" + hexes(value);
    }
}

Demo Results

Running the demo should produce exactly these results: 

Hello
0x0 == 0
0x400 == (0x00FEDC00 & -0x00FEDC00)
0x40000000 == (1 << 30)
-0x80000000 == 0x80000000
-0x123678a == 0xFEDC9876
-0x1 == -1
-0x1 == 0x123456789
OK
Hello again
0x7fffffff as base
0x7fffffff by owner
0x0 by group
0x0 by anyone
0x82000 by next owner
aka 532480
OK

Demo

To reproduce exactly the expected demo results above, run the demo code below.

We chose test cases that astonish people new to hex and test cases that astonish people new to LSL permission masks.

You'll get the permission mask results we show if you create a New Script to run this demo in. If instead you try modifying some old script to run this demo, then you might have to edit its permission masks to get the demo results that we show here. 

default
{
    state_entry()
    {
        llOwnerSay("Hello");
        llOwnerSay(hex(0) + " == 0");
        llOwnerSay(hex(0x00FEDC00 & -0x00FEDC00) + " == (0x00FEDC00 & -0x00FEDC00)");
        llOwnerSay(hex(1 << 30) + " == (1 << 30)");
        llOwnerSay(hex(0x80000000) + " == 0x80000000");
        llOwnerSay(hex(0xFEDC9876) + " == 0xFEDC9876");
        llOwnerSay(hex(-1) + " == -1");
        llOwnerSay(hex(0x123456789) + " == 0x123456789");
        llOwnerSay("OK");
        
        llOwnerSay("Hello again");
        string item = llGetScriptName();
        llOwnerSay(hex(llGetInventoryPermMask(item, MASK_BASE)) + " as base");
        llOwnerSay(hex(llGetInventoryPermMask(item, MASK_OWNER)) + " by owner");
        llOwnerSay(hex(llGetInventoryPermMask(item, MASK_GROUP)) + " by group");
        llOwnerSay(hex(llGetInventoryPermMask(item, MASK_EVERYONE)) + " by anyone");
        llOwnerSay(hex(llGetInventoryPermMask(item, MASK_NEXT)) + " by next owner");
        llOwnerSay("aka " + (string) llGetInventoryPermMask(item, MASK_NEXT));
        llOwnerSay("OK");
    }
}

Specification

We chose requirements that astonish people who usually write clever, small, or fast code by taking as precedent a specification from the far off world of people who usually write brief, clear, and conventional code.

We require exactly the same results as the hex function of the popular Python scripting language. We thus reproduce how hex integer literals often appear in LSL script, conforming to such arbitrary and traditional AT&T C conventions as:

  1. return lower case a b c d e f rather than upper case A B C D E F,
  2. return a signed 31-bit result if negative, rather than an unsigned 32-bit result,
  3. omit the leading zeroed nybbles, except return "0x0" rather than "0x" when the result is zero,
  4. return a meaningless "0" before the "x", as LSL and C compilers require,
  5. return the "x" on the left as in LSL and C, not the "h" on the right as in Assembly code, and
  6. return the nybbles listed from most to least significant as in English, not listed from least to most significant as in Arabic.

Brief doc for the Python hex function appears buried deep within http://docs.python.org/lib/built-in-funcs.html

Disputes over the detailed specification of the Python hex function appear buried deep within http://www.python.org/dev/peps/pep-0237/

Retrieved from "https://wiki.secondlife.com/w/index.php?title=Hex&oldid=1194824"