Difference between revisions of "Hex"

From Second Life Wiki
Jump to navigation Jump to search
(implement the Talk:Hex plan to reword for concise/ small/ fast for clarity, also strike the undefined term "operator" "executed")
m (<lsl> tag to <source>)
 
(37 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, the demo results, and the alternatives 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;">


Here you see code that implements the hex function specification, demo code that calls the hex function, and a copy of exactly the results you should see when you run the demo.
The brief, clear, conventional code here implements this specification exactly.
 
You see three kinds of code that implement the one specification. The concise & conventional code explains and implements the specification. The small code reduces the code size reported by llGetFreeMemory. The fast code reduces the run time reported by llGetTimestamp.
 
=== 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


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 57: 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 (0 < value)
     else // if (0 < value)
     {
     {
         return "0x" + bits2nybbles(value);
         return "0x" + hexes(value);
     }
     }
}
}
</pre>
</source>


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


FIXME milliseconds of run time to calculate "-0x80000000" reported by llGetTimestamp -- more than the small code and more than the fast code
<div id="box">


=== Small ===
== Demo Results ==
 
<div style="padding: 0.5em;">
You should choose this code when you care more about small & fast than about concise & conventional.


We wrote this small code to show how to reduce the code size reported by [[llGetFreeMemory]]. We think this small code produces the same results as the concise & conventional code. After adequate education & review, you should agree. Code to implement bits2nybbles may be smaller than the hexu code shown here.
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>


250 bytes of code reported by llGetFreeMemory -- less than the concise & conventional code and less than the fast code
</div>
</div>


FIXME milliseconds of run time to calculate "-0x80000000" reported by llGetTimestamp -- less than the concise & conventional code, but more than the fast code
<div id="box">


=== Fast ===
== Demo ==
 
<div style="padding: 0.5em;">
You should choose this code when you care more about fast & small than about concise & conventional.
 
We wrote this fast code to show how to reduce the run time reported by [[llGetTimestamp]]. We think this fast code produces the same results as the concise & conventional code. After adequate education & review, you should agree. This code leaves as little work inside the loop as possible. This code might not be as fast as code that unrolls the loop completely.
 
<pre>
// http://wiki.secondlife.com/wiki/hex
 
string XDIGITS = "0123456789abcdef"; // could be "0123456789ABCDEF"
 
string hexu(integer bits)
{
    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>
 
337 bytes of code reported by llGetFreeMemory - less than concise & conventional code, but more than the small code
 
FIXME milliseconds of run time to calculate "-0x80000000" reported by llGetTimestamp - less than the concise & conventional code and less than the small code


=====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 175: Line 134:
     }
     }
}
}
</pre>
</source>
 
=====Demo Results:=====
 
Running the demo 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>


</div>
</div>
Line 206: Line 141:
<div id="box">
<div id="box">


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


The specification requires exactly the same results as the hex function of the Python scripting language.
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.


The specification reproduces how hex integer literals often appear in LSL script, conforming to such arbitrary and traditional AT&T C conventions as:
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:


# 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 223: 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 a concise & conventional exemplar, experts find appropriate uses for the small & fast exemplars.
We don't know how to write LSL that implements a hex function that is as concise as our most concise, as conventional as our most conventional, as small as our smallest, and as fast as our fastest, all simultaneously. We think that goal is an impossibility.


</div>
</div>
Line 233: Line 164:
<div id="box">
<div id="box">


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


You can make the code smaller and faster still whenever you can accept the cost of abandoning the conventional specification.
'''Articles'''
 
* [[Efficient Hex]]
=== Different & Small - Signed Only ===
 
The history of this article says that this version somehow violates the specification, I don't yet see the difference myself. Possibly the intended contrast was with an unsigned hex implementation such as bits2nybbles or hexu.
 
<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>
 
197 bytes of code reported by llGetFreeMemory
 
FIXME milliseconds of run time to calculate "-0x80000000" reported by llGetTimestamp
 
=== 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 -- an assumption entirely outside the specification.
 
<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>
 
200 bytes of code reported by llGetFreeMemory
 
TBD milliseconds of run time to calculate "-0x80000000" reported by llGetTimestamp
 
</div>
</div>
 
<div id="box">
 
== See Also ==
<div style="padding: 0.5em">


'''Functions'''
'''Functions'''
Line 308: Line 174:
* [[llGetObjectPermMask]]
* [[llGetObjectPermMask]]
* [[llIntegerToBase64]]
* [[llIntegerToBase64]]
* [[llBase64ToInteger]]
 
* [[llGetFreeMemory]]
'''Wikipedia'''
* [[llGetTimestamp]]
* {{Wikipedia|Exemplar}}
* [[llMessageLinked]]
* {{Wikipedia|Principle_of_least_astonishment}}
* [[llList2Integer]]
* [[llList2String]]


</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"