Difference between revisions of "Hex"

From Second Life Wiki
Jump to navigation Jump to search
(quote the scientific repeatably measurable code size, not the astonishing plus four size naively measured by people who only add code to a nearly empty script)
m (<lsl> tag to <source>)
 
(38 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{LSL Header}}__NOTOC__
{{LSL Header}}
 
__TOC__


<div id="box">
<div id="box">
{{#vardefine:p_value_desc|signed value to be expressed as signed hex}}
{{#vardefine:p_value_desc|signed value to be expressed as negative or nonnegative hex}}
== Function: [[string]] hex([[integer]] {{LSL Param|value}}); ==
== Function: [[string]] hex([[integer]] {{LSL Param|value}}); ==
<div style="padding: 0.5em;">
<div style="padding: 0.5em;">
Line 13: 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.
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 was a work in progress as of 2007-10. The specification, the implementations, the demo, and the sample results may not yet be totally consistent. See the [[Talk:Hex|discussion]] tab.
</div>
</div>
</div>
</div>
Line 21: Line 21:
<div id="box">
<div id="box">


== Implementations ==
== Code ==
<div style="padding: 0.5em;">
<div style="padding: 0.5em;">
Below are several different versions of the same two functions, each has been optimized with a different use case. These use cases are titled with the common programing goals they highlight: Clear & Conventional, Fast, Small, and Different. Unfortunately with LSL it is typically very difficult if not impossible to write code that embodies all of these design goals but it is possible to achieve several of them.
The design specification only specifies one function with a specific interface, implementations that do not meet that requirement are marked as Different.


=== Clear & Conventional ===
The brief, clear, conventional code here implements this specification exactly.


You should feel this code is easy to review, and modify. Upon review it is easy to see this code conforms to the specification and is easy to read. Additionally the comments instruct the user on 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. The cost of this readability and easy of use is that the code runs substantially slower and has a larger memory footprint. Every other implementation runs faster then this one.
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


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


string bits2nybbles(integer bits)
string hexes(integer bits)
{
{
     string nybbles = "";
     string nybbles = "";
     while (bits)
     while (bits)
     {
     {
         integer lsbs = bits & 0xF;
         integer lsn = bits & 0xF; // least significant nybble
         string nybble = llGetSubString(XDIGITS, lsbs, lsbs);
         string nybble = llGetSubString(XDIGITS, lsn, lsn);
         nybbles = nybble + nybbles;
         nybbles = nybble + nybbles;
         bits = bits >> 4; // discard the least significant bits at right
         bits = bits >> 4; // discard the least significant bits at right
Line 54: Line 51:
     if (value < 0)
     if (value < 0)
     {
     {
         return "-0x" + bits2nybbles(-value);
         return "-0x" + hexes(-value);
     }
     }
     else if (value == 0)
     else if (value == 0)
     {
     {
         return "0x0"; // bits2nybbles(value) == "" when (value == 0)
         return "0x0"; // hexes(value) == "" when (value == 0)
     }
     }
     else // if (value > 0)
     else // if (0 < value)
     {
     {
         return "0x" + bits2nybbles(value);
         return "0x" + hexes(value);
     }
     }
}
}
</pre>
</source>


'''Size:''' 347 bytes<br/>
</div>
</div>


=== Small ===
<div id="box">


Here is a size optimized implementation. It has a reduced memory footprint but is slower then a Speed implementations.
== Demo Results ==
<div style="padding: 0.5em;">
 
Running the demo should produce exactly these results:


<pre>
<pre>
// http://wiki.secondlife.com/wiki/hex
Hello
 
0x0 == 0
string hexu(integer bits)
0x400 == (0x00FEDC00 & -0x00FEDC00)
{
0x40000000 == (1 << 30)
    string nybbles = "";
-0x80000000 == 0x80000000
    do
-0x123678a == 0xFEDC9876
    {
-0x1 == -1
        integer index = bits & 0xF;
-0x1 == 0x123456789
        nybbles = llGetSubString("0123456789abcdef", index, index) + nybbles;
OK
    } while ((bits = (0xfffFFFF & (bits >> 4))));
Hello again
    return "0x" + nybbles;
0x7fffffff as base
}
0x7fffffff by owner
 
0x0 by group
string hex(integer value)
0x0 by anyone
{
0x82000 by next owner
    //saves one byte over "value < 0" and is faster.
aka 532480
    if (value & 0x80000000) return "-" + hexu(-value);
OK
    return hexu(value);
}
</pre>
</pre>


'''Size:''' 250 bytes<br/>
</div>
</div>


=== Fast ===
<div id="box">


In this implementation the readability and size have been scarified for speed. At execution, from call to return the fewest number of operators are executed, specifically the loop has been setup to use the fewest number of operators per iteration. In the double function category, this is the fastest implementation.
== Demo ==
<div style="padding: 0.5em;">


<pre>
To reproduce exactly the expected demo results above, run the demo code below.
// http://wiki.secondlife.com/wiki/hex


string XDIGITS = "0123456789abcdef"; // could be "0123456789ABCDEF"
We chose test cases that astonish people new to hex and test cases that astonish people new to LSL permission masks.


string hexu(integer bits)
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.
{
    integer index = (bits & 0xF);
    string nybbles = llGetSubString(XDIGITS, index, index);
    if ((bits = (0xfffFFFF & (bits >> 4))))
    {
        do
        {
            nybbles = llGetSubString(XDIGITS, index = (bits & 0xF), index) + nybbles;
        } while ((bits = (bits >> 4)));
    }
    return "0x" + nybbles;
}
 
string hex(integer value)
{
    //saves one byte over "value < 0" and is faster.
    if (value & 0x80000000) return "-" + hexu(-value);
    return hexu(value);
}
</pre>
 
'''Size:''' 337 bytes<br/>
 
=====Demo=====


This demo script shows some interesting test cases for the hex function and the permission masks of the script.
<source lang="lsl2">
 
<pre>
default
default
{
{
Line 160: Line 134:
     }
     }
}
}
</pre>
</source>
 
=====Demo Results:=====
 
Running the demo script to call your choice of code should produce exactly these results:
 
<pre>
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
</pre>


=====Note:=====
If you are using an implementation that doesn't conform to the specification the demo script may not compile or give the same results.
</div>
</div>
</div>
</div>
Line 193: Line 141:
<div id="box">
<div id="box">


== Design Rationale ==
== Specification ==
<div style="padding: 0.5em">
<div style="padding: 0.5em;">


The first few implementations we present do conform to our 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.


Our specification requires exactly the same results as the hex function of the Python scripting language.
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:
 
This 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 213: Line 159:
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/


There are multiple implementations because LSL is inadequate to produce a version that is optimal in the majority of popular use cases.
</div>
</div>
</div>
</div>
Line 219: Line 164:
<div id="box">
<div id="box">


== Alternatives ==
== See Also ==
<div style="padding: 0.5em;">
<div style="padding: 0.5em;">


=== Different & Small - Signed Only ===
'''Articles'''
 
* [[Efficient Hex]]
Rumour tells us this version returns results that differ somehow, I don't yet see the difference myself.
 
Here is an optimized implementation that only uses a single function, this provides an additional reduction to the memory footprint.
 
<pre>
// http://wiki.secondlife.com/wiki/hex
 
string hex(integer value)
{
    string lead = "0x";
    if(value & 0x80000000)
    {//saves one byte over "value < 0" and is faster.
        lead = "-0x";
        value = -value;
    }
    string nybbles = "";
    do
    {
        integer index = value & 0xF;
        nybbles = llGetSubString("0123456789abcdef", index, index) + nybbles;
    } while ((value = (0xfffFFFF & (value >> 4))));
    return lead + nybbles;
}
</pre>
 
'''LSO Size:''' 197 bytes<br/>
 
=== Different & Small - Signed or Unsigned ===
 
This version returns a signed or an unsigned result, whichever you prefer.
 
Here is a version where the calling interface has been changed to allow for the two functions to be merged. This merge allows for a considerable savings in bytecode. This savings evaporates if the function is explicitly called from more than 10 places in the script (as compared to the double function size implementation). This of course assumes you need both sets of functionality.
 
<pre>
// http://wiki.secondlife.com/wiki/hex
 
string hex(integer value, integer signed)
{
    string lead = "0x";
    if((value & 0x80000000) && signed)
    {//saves one byte over "value < 0" and is faster.
        lead = "-0x";
        value = -value;
    }
    string nybbles = "";
    do //variable recycling is ugly but it saves bytecode
        nybbles = llGetSubString("0123456789abcdef", signed = (value & 0xF), signed) + nybbles;
    while ((value = (0xfffFFFF & (value >> 4))));
    return lead + nybbles;
}
</pre>
 
'''LSO Size:''' 200 bytes<br/>
 
</div>
</div>
 
<div id="box">
 
== See Also ==
<div style="padding: 0.5em">


'''Functions'''
'''Functions'''
Line 290: Line 174:
* [[llGetObjectPermMask]]
* [[llGetObjectPermMask]]
* [[llIntegerToBase64]]
* [[llIntegerToBase64]]
* [[llBase64ToInteger]]
 
* [[llMessageLinked]]
'''Wikipedia'''
* [[llList2Integer]]
* {{Wikipedia|Exemplar}}
* [[llList2String]]
* {{Wikipedia|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"