Subject: [mmox] Details proposal

From: Catherine Pfeffer <[email-masked]>
Date: Wed, 25 Feb 2009 02:43:39 +0100

Hi all,

Infinity asked me to write down proposals to make LLSD a bit better.

Honestly, I don't think it is really the way to go. I think the previous
message has shown how much the current XML serialization is unsatisfying,
due to the 1:1 paradigm.

But I have promised to do such a proposal, so here we go:
1 - change the name from LLSD to VWSD
2 - add provision for different sizes for integers and floats. In XML that
could mean an extra size="" attribute with a default to 32 bits so it needs
not be specified in the majority of cases, in binary serialization that
would mean new data codes
3 - add provision for unsigned data. In XML that would mean an extra
signed="" attribute with a default to "yes" so it needs not be specified in
the majority of cases, in the binary serialization that calls for more data
codes too
4 - allow some shortcuts for an array of three reals <vector> and an array
of 4 reals <quat>
5 - embed map entries into <e> ... </e> tags

That's almost the same points as the ones that Jon has listed.

But again, to do it in a real XML-ish way, the data types like <integer>
should move to the DTD. I don't see any justification for them in an XML
file.

-- 
Cathy

---

From: Jon Watte <[email-masked]>
Date: Tue, 24 Feb 2009 18:07:39 -0800

Catherine Pfeffer wrote:
> But again, to do it in a real XML-ish way, the data types like 
> <integer> should move to the DTD. I don't see any justification for 
> them in an XML file.

Can you view a "xxSD" specification file as an alternative DTD? I e, the 
output of a specific xxSD file could be one or more of the following:
1) C++ source code that can marshal/demarshal structs to various 
serializations
2) An XML DTD
3) Python code that uses module "struct" and "xml.dom.minidom" to 
translate between XML and struct formats
...

However, I think that you still haven't addressed one big concern, which 
is the schema-dependent transmission format. Given your XML-ish version 
of a packet, in binary, it could look something like:

<type:AgentData> 1 byte <prop-count: 4> 1 byte
<prop: Agent-id> 1 byte <some UUID> 16 bytes
<prop: GroupId> 1 byte <vari-int: 0> 1 byte
<prop: Session-id> 1 byte <some UUID> 16 bytes
<prop: ObjectData> 1 byte <prop-count: 11> 1 byte
<prop: BypassRaycast> 1 byte <vari-int: 1> 1 byte
<prop: EveryoneMask> 1 byte <vari-int: 0> 1 byte
<prop: Flags> 1 byte <vari-int: 2> 1 byte  (!)
<prop: GroupMask> 1 byte <vari-int: 0> 1 byte
<prop: Material> 1 byte <vari-int: 3> 1 byte
<prop: NextOwnerMask> 1 byte <vari-int: 0x8C000> 3 bytes
<prop: PCode> 1 byte <vari-int: 9> 1 byte
<prop: Path> 1 byte <prop-count: 15> 1 byte
<prop: Begin> 1 byte <vari-int: 0> 1 byte
<prop: Curve> 1 byte < vari-int: 16> 1 byte
<prop: End> 1 byte <vari-int: 0> 1 byte
<prop: RadiusOffset> 1 byte <vari-int: 0> 1 byte
<prop: Revolutions> 1 byte <vari-int: 0> 1 byte
<prop: ScaleX> 1 byte <vari-int: 100> 1 byte
<prop: ScaleY> 1 byte <vari-int: 100> 1 byte
<prop: ScaleZ> 1 byte <vari-int: 0> 1 byte
<prop: ShearX> 1 byte <vari-int: 0> 1 byte
<prop: ShearY> 1 byte <vari-int: 0> 1 byte
<prop: Skew> 1 byte <vari-int: 0> 1 byte
<prop: TaperX> 1 byte <vari-int: 0> 1 byte
<prop: TaperY> 1 byte <vari-int: 0> 1 byte
<prop: Twist> 1 byte <vari-int: 0> 1 byte
<prop: TwistBegin> 1 byte <vari-int: 0> 1 byte
<prop: Profile> 1 byte <prop-count: 4> 1 byte
<prop: Begin> 1 byte <vari-int: 0> 1 byte
<prop: Curve> 1 byte <vari-int: 1> 1 byte
<prop: End> 1 byte <vari-int: 0> 1 byte
<prop: Hollow> 1 byte <vari-int: 0> 1 byte
<prop: RayEnd> 1 byte <double: 42.9329986572265625> 8 bytes <double: 
29.6600322723388671875> 8 bytes <double: 31.399318695068359375> 8 bytes 
<vari-int: 0> 1 byte
<prop: RayStart> 1 byte <double: 48.281482696533203125> 8 bytes <double: 
32.063152313232421875> 8 bytes <double: 34.092010498046875> 8 bytes
<prop: RayTargetId> 1 byte <uuid: ""> 16 bytes
<prop: Rotation> 1 byte <fp16: 0> 2 bytes <fp16: 0> 2 bytes <fp16: 0> 2 
bytes <fp16: 1> 2 bytes
<prop: Scale> 1 byte <fp16: 0.5> 2 bytes <fp16: 0.5> 2 bytes <fp16: 0.5> 
2 bytes
<prop: State> 1 byte <vari-int: 0> 1 byte

If I have counted right, that's 184 bytes, for a nice 600% savings over 
the XML-ish form, which in turn is a 250% savings over the "straight 
serialization" version. You could easily cut it in half or more by not 
sending default/empty properties, and by sending fp32, not double, for 
data values.

Note that this encoding saves space in a few ways:

1) It uses the knowledge that the destination will have the schema to 
encode property references using small, context-dependent integers.

2) It uses the knowledge that each property has a defined type to avoid 
encoding the type explicitly.

3) It uses vari-int encoding (basically Google protocol buffers, but 
putting a sign bit in the first byte if the value is not in the 0..127 
"optimized" range).

4) It uses fp16 for quaternions. There really is no reason to use more 
than that -- in fact, a fixed-point representation could probably get 
away with even less. For example 10 bits each for three components in 
the range [-0.78..0.78], and 2 bits telling you which component was 
dropped (you drop the biggest component, so the second-biggest is known 
to be smaller than sqrt(2)), and then re-construct by knowing it's 
normalized. But maybe going to that extreme for that particular datatype 
is overkill in the interoperability context :-)

I think that the implicit knowledge of 1) and 2) are the important 
concepts to take away here, because they account for most of the savings.

Sincerely,

jw

---

From: "Meadhbh Hamrick (Infinity)" <[email-masked]>
Date: Tue, 24 Feb 2009 19:45:26 -0800

so... hope you don't mind.. i'm responding to different aspects of  
this proposal with different emails

i'm sure some of my co-workers will pelt me with rotten vegetables for  
giving in, but sure, an affiliation neutral name ending in "SD" is  
something we can probably live with and is probably also appropriate.  
however.... i believe that to avoid confusion, we may want to keep the  
draft-llsd-hamrick-XX.txt naming scheme for just the FILE NAMES used  
in the ID repository. these things disappear after 6 months, so a year  
after we find consensus and the RFC goes through, we'll all have  
forgotten we ever considered the LLSD name.

with tongue firmly in cheek, however, i might also suggest "XXSD" as  
it seems to have also gotten some mention in emails lately.

On Feb 24, 2009, at 5:43 PM, Catherine Pfeffer wrote:

> Honestly, I don't think it is really the way to go. I think the  
> previous message has shown how much the current XML serialization is  
> unsatisfying, due to the 1:1 paradigm.
>
> 2 - add provision for different sizes for integers and floats. In  
> XML that could mean an extra size="" attribute with a default to 32  
> bits so it needs not be specified in the majority of cases, in  
> binary serialization that would mean new data codes
> signed="" attribute with a default to "yes" so it needs not be  
> specified in the majority of cases, in the binary serialization that  
> calls for more data codes too
> 4 - allow some shortcuts for an array of three reals <vector> and an  
> array of 4 reals <quat>
> _______________________________________________
> mmox mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mmox

---

From: "Meadhbh Hamrick (Infinity)" <[email-masked]>
Date: Tue, 24 Feb 2009 19:49:47 -0800

about sizes of ints as attributes.

let me pose the question... what is the difference in terms of  
processing expectations if one sends

'<integer size="8">12</integer>'

vs. sending

'<integer size="32">12</integer>' ?

do we want to be in the business of mandating that the receiver  
actually check to see if the value is representable with the number of  
bits given, or do we just want to store the value somewhere?

and what about '<integer size="13">12</integer>' ? and what about  
"<integer size="4096">12</integer>"?

if we allow that last fragment, and we require receivers to honor the  
size, then implementers MUST use arbitrary lengthed integers (i.e.  
bignum packages.) and it's hard to say things like "we're concerned  
about the efficiency of the XML parsing" while you're also saying  
"yeah... all ints should be bignums."

but if we say something like.. "all right, we'll just limit the size  
to being a max of 128 bits," then we're effectively doing the same  
thing because not all languages that people would want to use (like  
python and PHP) support even native 64 bit ints.

so unless we say that ints are at most 32 bits, then our python and  
PHP LLSD implementations will REQUIRE the use of bignums.

so let me now pose another the question...

what would happen if we just remove the bit width of number types from  
the proposal all together? would that kill anyone?

it would, i believe, mandate an error condition be signaled should the  
remote peer send an encoding of an integer that you can't represent.  
or maybe you just do some magic behind the scenes and dynamically  
convert to a bignum if you're language supports it.

or maybe we just drop that value on the floor? we say... "if you pass  
some pre-defined limit, you get the default value"

this might be doable if everyone understood that when you're  
connecting to second life, we have so much python and PHP we're gonna  
freak if you start using 64 bit ints and double double floats, but  
when you connect to OSGrid, 64 bit ints are fine.

or you could do some sort of negotiation up front asking the peer,  
"what's your preferred and maximum integer and float size?"

it is unfortunate that all of these options are sub-optimal, but  
that's what it looks like to me.

about signedness

assuming we can all find agreement that the machines we're using all  
use 2's complement notation, the main difference between signed and  
unsigned seems to be behavior when a right shift operation occurs.

couldn't we just say that when an endpoint needs a value to be a  
signed value, it stores it in a signed integral container and when it  
needs it to be an unsigned value, it stores it in an unsigned integral  
container?

---

From: Dan Olivares <[email-masked]>
Date: Wed, 25 Feb 2009 00:04:18 -0500

To understand why there would be a request for this, you also have to
understand some of the issues that people have delt with when working
with LLSD.

Take boolean values encoded uints for instance.   Often times in the
current use of LLSD, uints are used to transfer several bit values
encoded into a 32 bit unsigned integer.   Additionally, there's
currently no way to represent an unsigned integer in LLSD.  This means
that you must represent it as a base64 encoded byte array and often
results in ugly, non human readable XML Serializations, for example,
in parcels;
<key>ParcelFlags</key><binary encoding="base64">fiAESw==</binary>

Then, you also have a single uint value that represents the ID of the
auction associated with the parcel that is also encoded as a base64
encoded object.  This is not a group of encoded boolean values, this
is a single value.
<key>AuctionID</key><binary encoding="base64">AAAAAA==</binary>

Then, you have 64 bit unsigned integers (aka,  bignums) that are
represented with base64 encoded binary;
<key>Handle</key><binary encoding="base64">AAIkAAAEJAA=</binary>

Then, you have IP addresses that are represented with base64 encoded binary;
<key>IP</key><binary encoding="base64">2FIQPA==</binary>

Then, you have Timestamps that are represented with base64 encoded binary;
<key>TimeStamp</key><binary encoding="base64">SLs0lw==</binary>

Then, you have bitmap data, that is also represented with base64 encoded binary;
<key>Bitmap</key><binary
encoding="base64">AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAwD8AAAAAAADAPwAAAAAAAMA/AAAAAAAAwD8AAAAAAADAPwAAAAAAAMA/AAAAAAAAwD8AAAAAAADAPwAAAAAAAMA/AAAAAAAAwD8AAAAAAADAPwAAAAAAAOA/AAAAAAAA4D8AAAAAAADgPwAAAAAAAAAAAAAAAAAAAAA=</binary>

Do you see how ambiguous the "binary" type is?.   In my opinion, the
only valid use of it in an XML encoding listed above, is the bitmap.
XML encodings are /meant/ to be as human readable as possible.

Then, you have boolean values that are represented as integers;
<key>MediaAutoScale</key><integer>1</integer>

Then, in addition to having timestamp values represented in the binary
encoding, you also have unix time since epoch values represented as a
'real'
<key>start_time</key><real>1232962915.3859558</real>

In terms of a 'parcel' on LLGrid (which is a cut unit of land where
you can define specific settings as well as sell, purchase, ban, etc),
the settings of the parcel are represented by a set of boolean values.
 These boolean values are encoded into a 32 bit unsigned integer
called "ParcelFlags".   (A few of of the 32 acceptable boolean values
are: AllowDamage AllowAPrimitiveEntry AllowDeedToGroup AllowFly
CreateObjects ForSale AllowGroupScripts).
over LLSD, this looks like;
<key>ParcelFlags</key><binary encoding="base64">fiAESw==</binary>.

However, if that wasn't complicated and unreadable enough..    It
turns out that all unsigned integer values are also represented /big
endian/ and integers are represented /little endian/.   Therefore, to
be able to actually use those values, you have to;

1. Know the agreed upon encoding, (which bits refer to which boolean flags)
2. You must convert it from the non human readable "fiAESw==" into an
array of bytes
3. You must convert it to your system's 'endian-ness'
4. You must use bitwise operations to decode the flags.

There are a plethora of types of values that use this human
non-readable boolean value encoding on things ranging from region
settings, to object data, to permissions.  They're all over the place.

So, that's the issue that I'm trying to solve when I ask for more
datatypes and more specific data types.  There's also use consistancy
issues and mentioned above and key naming consistency issues in
existing uses of LLSD.    Something can be named 'AgentID' in one CAP
name/value key, and named 'agent_id' in another.

Best Regards

Daniel Olivares

On Tue, Feb 24, 2009 at 10:49 PM, Meadhbh Hamrick (Infinity)
<[email-masked]> wrote:
> let me pose the question... what is the difference in terms of processing
> expectations if one sends
>
> do we want to be in the business of mandating that the receiver actually
> check to see if the value is representable with the number of bits given, or
> do we just want to store the value somewhere?
>
> and what about '<integer size="13">12</integer>' ? and what about "<integer
> size="4096">12</integer>"?
>
> if we allow that last fragment, and we require receivers to honor the size,
> then implementers MUST use arbitrary lengthed integers (i.e. bignum
> packages.) and it's hard to say things like "we're concerned about the
> efficiency of the XML parsing" while you're also saying "yeah... all ints
> should be bignums."
>
> but if we say something like.. "all right, we'll just limit the size to
> being a max of 128 bits," then we're effectively doing the same thing
> because not all languages that people would want to use (like python and
> PHP) support even native 64 bit ints.
>
> so unless we say that ints are at most 32 bits, then our python and PHP LLSD
> implementations will REQUIRE the use of bignums.
>
> what would happen if we just remove the bit width of number types from the
> proposal all together? would that kill anyone?
>
> remote peer send an encoding of an integer that you can't represent. or
> maybe you just do some magic behind the scenes and dynamically convert to a
> bignum if you're language supports it.
>
> or maybe we just drop that value on the floor? we say... "if you pass some
> pre-defined limit, you get the default value"
>
> this might be doable if everyone understood that when you're connecting to
> second life, we have so much python and PHP we're gonna freak if you start
> using 64 bit ints and double double floats, but when you connect to OSGrid,
> 64 bit ints are fine.
>
> or you could do some sort of negotiation up front asking the peer, "what's
> your preferred and maximum integer and float size?"
>
> it is unfortunate that all of these options are sub-optimal, but that's what
> it looks like to me.
>
> about signedness
>
> assuming we can all find agreement that the machines we're using all use 2's
> complement notation, the main difference between signed and unsigned seems
> to be behavior when a right shift operation occurs.
>
> couldn't we just say that when an endpoint needs a value to be a signed
> value, it stores it in a signed integral container and when it needs it to
> be an unsigned value, it stores it in an unsigned integral container?
>

---

From: Dan Olivares <[email-masked]>
Date: Wed, 25 Feb 2009 00:17:31 -0500

I'm good either way here really.   LLSD, XXSD, VWSD.    The naming
really doesn't matter much to me.   Changing it from LLSD to XXSD
might make more people feel comfortable that it isn't 'weighted' in
the direction of Linden Lab.  This may also have an effect on uptake.

Best Regards

Daniel Olivares

On Tue, Feb 24, 2009 at 10:45 PM, Meadhbh Hamrick (Infinity)
<[email-masked]> wrote:
> so... hope you don't mind.. i'm responding to different aspects of this
> proposal with different emails
>
> giving in, but sure, an affiliation neutral name ending in "SD" is something
> we can probably live with and is probably also appropriate. however.... i
> believe that to avoid confusion, we may want to keep the
> draft-llsd-hamrick-XX.txt naming scheme for just the FILE NAMES used in the
> ID repository. these things disappear after 6 months, so a year after we
> find consensus and the RFC goes through, we'll all have forgotten we ever
> considered the LLSD name.
>
> with tongue firmly in cheek, however, i might also suggest "XXSD" as it
> seems to have also gotten some mention in emails lately.
>

---

From: "Meadhbh Hamrick (Infinity)" <[email-masked]>
Date: Tue, 24 Feb 2009 22:46:06 -0800

okay. you've sold me! i propose we don't do this again and i will seek  
out and pelt with rotten vegetables the linden developer who wants to  
perpetuate **** like this.

	* there are very good reasons why parcel flags should be an array or  
map of booleans. not the least of which is you can do something like  
this in the code:

		if( parcelFlags.at("allow_fly").asBoolean() ) {
			System.out.println( "you may now fly about the parcel.\n");
		}

	* we're thinking that auctions should be represented by URIs in the  
future.

	* we're also thinking about eliminating 64 bit ints from the  
protocol. in most places where the 64 bit ints were used, UUIDs were  
more appropriate.

	* IP addresses? krikey! how 'bout URIs!

	* timestamps? we have a date type, let's use it!

	* and a bitmap? if it was any larger i would recommend we reference  
the URI where the peer could find the resource (which is nice, cause  
we also get the mime type)

but... i'm not trying to give flip answers here, only to say:

	* yes. our protocol is "sub optimal." irrespective of what happens  
here, we're changing it to be more optimal.
	* if we can honestly say we've come to the point where our biggest  
concern is 64-bit ints, and not stuff like what you pulled out of the  
bag of pain below, i will be very, very happy

-cheers
-meadhbh

On Feb 24, 2009, at 9:04 PM, Dan Olivares wrote:

>> actually
>> PHP LLSD
>> connecting to
>> "what's
>> signed
>>> previous
>>> XML that
>>> specified in
>>> <integer>

---

From: Jon Watte <[email-masked]>
Date: Wed, 25 Feb 2009 11:00:43 -0800

> '<integer size="32">12</integer>' ?

If we go with a schema-based approach (where "schema" could refer to the 
xxSD source file, not necessarily an XSD or DTD), then you don't need to 
send the size for each field. Instead, the schema defines what the 
"internal" format is, and the size does not need to be sent.

<value key="month">12</value>

> the proposal all together? would that kill anyone?

I believe bit width is necessary for the schema, so that I can a priori 
determine whether I'm actually capable of handling the kind of data that 
someone might send to me. If the schema says "this is a 4096-bit int" 
and I don't deal with 4096-bit ints, I want to know that when 
establishing the connection or looking at the schema, not when I get an 
XML document with hundreds of digits in an "integer" value field.

> unsigned seems to be behavior when a right shift operation occurs.

There are transmission encoding problems with that, though, as you can't 
optimize the transmission length for small negative numbers (when 
sending binary). The Google protocol buffers format has that problem. 
The slight variation I proposed (that adds a sign bit and sends negative 
numbers in 1's complement) fixes that, at effectively no cost.

Sincerely,

jw

---

From: "Meadhbh Hamrick (Infinity)" <[email-masked]>
Date: Wed, 25 Feb 2009 11:09:10 -0800

yeah. i think the question i was eventually going to ask was..

a. do we need to define the size of integers in the specification?
	- or is it okay for me to say.. "if you connect to Second Life, i  
will insist that integers are 32 bits." and for OSGrid to say "if you  
connect to OSGrid, i will insist that integers are 64 bits."
	- cause for what it's worth, the JSON spec doesn't provide size  
limits for numbers, so we're going to be defining that "somewhere" for  
JSON.

On Feb 25, 2009, at 11:00 AM, Jon Watte wrote:

> If we go with a schema-based approach (where "schema" could refer to  
> the xxSD source file, not necessarily an XSD or DTD), then you don't  
> need to send the size for each field. Instead, the schema defines  
> what the "internal" format is, and the size does not need to be sent.
>
>> what would happen if we just remove the bit width of number types  
>> from the proposal all together? would that kill anyone?
>>
>
> I believe bit width is necessary for the schema, so that I can a  
> priori determine whether I'm actually capable of handling the kind  
> of data that someone might send to me. If the schema says "this is a  
> 4096-bit int" and I don't deal with 4096-bit ints, I want to know  
> that when establishing the connection or looking at the schema, not  
> when I get an XML document with hundreds of digits in an "integer"  
> value field.
>
>
>> assuming we can all find agreement that the machines we're using  
>> all use 2's complement notation, the main difference between signed  
>> and unsigned seems to be behavior when a right shift operation  
>> occurs.
>>
>
> There are transmission encoding problems with that, though, as you  
> can't optimize the transmission length for small negative numbers  
> (when sending binary). The Google protocol buffers format has that  
> problem. The slight variation I proposed (that adds a sign bit and  
> sends negative numbers in 1's complement) fixes that, at effectively  
> no cost.
>
> Sincerely,
>
> jw
>

---

From: Jon Watte <[email-masked]>
Date: Wed, 25 Feb 2009 11:20:20 -0800

> connect to OSGrid, i will insist that integers are 64 bits."

I don't think that's smart, because sometimes an integer value only 
needs to be one byte. In OLIVE we specify integers with a bit-precision 
representation -- a 13-bit int is nothing special to us. Our internal 
IDL compiles to structures that arrange and pad integers based on 
declared size. We don't do integers bigger than 64 bits, though.
I'm prepared to relax this to 'integers are one of the basic types' (8, 
16, 32 or 64 bits, signed or unsigned) for purposes of interoperability, 
but I think that specifying integer ranges in the declaration of 
messages is necessary, or you'll have to treat every integer field as 
possibly being the worst case (64 bits signed).

Sincerely,

jw