Working with string or other values

[Wyzix33]

Hi, I'm trying to implement packBytes into my workflow and was wandering if it's possible to encode strings or other data like objects or arrays. Also how can i process values like 12345678901?
this is what i did:

const packBytes = (obj) => {
 const bits = [];
 const bitsVals = Object.values(obj).reduce((arr, val) => {
  const bit = Math.floor(val ? Math.log2(val) + 1 : 1);
  bits.push(bit);
  arr.push(bit, val);
  return arr;
 }, []);
 return [bits, bitsVals.reduce((byte, val, i) => (i % 2 ? byte + val : byte << val), 0) >>> 0];
};

const [bits, packed] = packBytes(data);

const unpacked = unpackBytes(packed, ...bits);

and i get the bits and the packed data, but it's not working for big integers, strings or anything else, any ideas on how to solve this?
And if we sort this out we can make a recursive function to process object values like arrays or other objects too and maybe use a custom character to split those custom values so they can have variable length..
Just wandering if this is possible..
Thanks

[e3dio]

Update: this discussion is outdated, PackBytes now has a new schema system

From your code it looks like you are trying to automatically determine the number of bits needed for the field based on the value of the field for each item individually. You are doing that with this line:

const bit = Math.floor(val ? Math.log2(val) + 1 : 1);

This is a misconception on how it works. Your encoding function and decoding function should know before doing the encoding and decoding what the bit sizes are. It's a schema you design in advance. If you generate bit sizes for every value then you have to send bit sizes with the data to decode it, this will double the size sent and makes no sense

wondering if it's possible to encode strings or other data like objects or arrays

I use packBytes to take large JSON objects provided from a different source and compress them down 25 or 50 times smaller, the JSON has objects and arrays and strings in it etc. You simply loop through the arrays and objects and add them to your buffer 1 at a time, nothing complicated about it. You need to manually code this process though, looks like you are trying automate everything with a single simple encoding function, but each field has different needs, it's more of a manual process for each field. Usually each field has different optimizations you can make before encoding the value to reduce the size, your decoder then does the reverse process to get original value

encode strings

Buffer has the buf.write(string) method to write strings into the buffer. If you write a string into the middle of a buffer you need to also add the length of the string so it knows when the string ends. Usually you do this by adding the string length to the buffer first, then write the string. Your decoding function looks at how long the string is, then decodes the string by slicing the buffer at that position and length. Strings take up a lot of space so ideally map strings to integers if possible

Also how can i process values like 12345678901

This value needs 34 bits so is outside the 32 bit range for packBytes. For this number I would use the Buffer writeUIntBE function which lets you write custom number of bytes, for this it needs 5 bytes. It will be less efficient than ideal because it wastes 6 bits, but it's a better option than writeBigUInt64BE which uses 8 bytes and would waste 30 bits. However if your data target is the web browser DataView can only decode 32 and 64 bit numbers so the 5 bytes encode won't work for that, in that case use the writeBigUInt64BE. I had a packBytes64 function that could pack 64 bits into 1 space but I removed it because it's slower and usually you don't need it, I could possibly add it back in

[Wyzix33]

Hi,
Thanks for your answer, yes, I'm trying to create a generic function that will encode a variable (int, string, array, object) and be able to decode it later, and from your example i understand i need the bits array to pack and unpack it... so i was trying to generate that array when packing and use it to unpack... Is this possible or it's too hard to create a function to pack a custom object that contains strings, arrays or other objects as values?
As i see it we can create a map using some kind of special characters to split special types something like this

s = a special character meaning from this point until the next occurrence we have a string
a = a special character meaning from this point until the next occurrence we have an array
o = a special character meaning from this point until the next occurrence we have an object

and the encoded data will be something like this

1111111s222222sa333333333aos444444444sa55555555555ao66666666oo

translating to:
we have some ints in the 1,
a string inside 2,
an array inside 3 that can include simple ints, strings, arrays, and objects
an object that includes a string on the first property 4, an array on second property 5 and another object on third property 6 (the array and object can also include other arrays and/or objects)

I understand now, so the bits number will have to be a fixed value based on the field type so

• bool, int8, uint8 = 1 bit
• int16, uint16 = 2 bit
• int32, uint32, float32 = 4 bit
• float64 = 8 bit

and strings or other values bigger than int32 it would have to be the bits of each character ?

for example

• ASCII character x = 7 bits
  and we will have to add

 const data = {
   field1: "aaa" // 7+7+7 = 21 bits
}; 

or can we convert the character ASCII Code (120 for x) and send that as 1 bit, but then how would we know this int is a character code maybe use a specific split char for example and know that everything between those split characters are ASCII codes and decode them as letters or characters... so "aaa" will have to end up |aaa| // 7+7+7+7+7 = 35 bits

and how can we send an array with x elements is it safe to use a custom character, delimiter, so that we know that all values between are array elements and decode them inside an array something like this:

{
  0:  first value,
  1: [ first array value, second array value, ....
  2: ...
}

or the best way is to send the arrays elements as a separate transmission, but for array of objects inside array of objects that will be quite hard to manage...

Thanks for your time

[e3dio]

from your example i understand i need the bits array to pack and unpack it... so i was trying to generate that array when packing and use it to unpack

Your encoding function and decoding function should know ahead of time before doing the encoding and decoding what the bit sizes are. It's a schema you design in advance. If you generate bit sizes for every value then you have to send bit sizes with the data to decode it, this will double the size sent and makes no sense. Hopefully this makes sense to you. You posted example data here before that you wanted to encode, I think the best thing would be for me to show you how I would encode example data, if you want to post example data here I could do that

[Wyzix33]

Here is the original object so you can understand better, I've translated all strings to ints and i have them available on the client browser, so i just need to send a bunch of objects that contains array of objects with ints and floats values

{
 "_id" : ObjectId("6291ff2dee2b7aec3b7070a5"),
 "type" : "FeatureCollection",
 "features" : [ 
     {
         "id" : "BE",
         "type" : "Feature",
         "geometry" : {
             "type" : "MultiPolygon",
             "coordinates" : [ 
                 [ 
                     [ 
                         [ 6.01991571473328, 50.7536455777936], 
                         [ 6.00146432981927, 50.7529502929202], 
                         [ 5.98266589691314, 50.7524013765143], 
                         ...
                     ]
                 ], 
                 [ 
                     [ 
                         [ 4.925853, 51.442709 ], 
                         [ 4.923032, 51.447411 ], 
                         [ 4.917302, 51.435413 ], 
                         [ 4.939683, 51.430785 ], 
                         [ 4.938087, 51.444699 ], 
                         [ 4.925853, 51.442709],
                         ...
                     ]
                 ]
             ]
         },
         "properties" : {
             "CNTR_NAME" : "Belgien-Belgique-België",
             "ISO3_CODE" : "BEL",
             "CNTR_ID" : "BE",
             "NAME_ENGL" : "Belgium"
         },
     }
 ]
}

all objects are the same, only the arrays lengths differs so i wanted to pack the object and send something like this

o._id | o.type | o.features.id | o.features.type | o.features.geometry.type | o.features.geometry.coordinates

o._id is a mongodb _id and needs to be sent as string
o.type, o.features.id, o.features.type, o.features.geometry.type are simple ints
o.features.geometry.coordinates is a array of arrays and i need to be able to unpack them as arrays, also the coordinates can have anything between 2 and 14 decimals, depending on accuracy...

so i was trying to create a function or a class that will scan my object, create a schema and then pack everything, on client i will need to have that schema to unpack and recreate my object translating the values to object properties.
Ideally i will just feed my object or array of same objects to a function, get back the schema and packed data and send the schema alongside the packed data to my client using websocket where only based on the schema i can unpack and get the same thing i packed.
But if i will be able at least to send the minimum i need (o._id | o.type | o.features.id | o.features.type | o.features.geometry.type | o.features.geometry.coordinates) i can recreate the object on the client from those.
Thanks

[Wyzix33]

Sending once the schema for an array of objects it's not to expensive, so for something like this

[
{ a: 1, b:2,c:3},
{a:4,b:5,c:6},
...
]

the schema will only be for one object and if there are hundreds or more objects in that array it should be ok

[e3dio]

o._id is a mongodb _id and needs to be sent as string

MongoDB ObjectID's are 12 byte binary blobs of data, when represented as a Hex string it takes up 24 characters = 24 bytes, double the size. This is where binary encoding is useful, you can encode this as the original 12 byte binary blob and it will take up 50% the size, then decode back to hex string

o.type, o.features.id, o.features.type, o.features.geometry.type are simple ints

The question here is how many possible ints are there for each set, use this for the bit size for the field

coordinates can have anything between 2 and 14 decimals, depending on accuracy

I also encode datasets with coordinates, this will be the biggest part of your data from your example so you need to minimize this as much as possible. I don't think you have looked at this yet, because 14 decimal places is equal to 1/1,000,000 of a millimeter, 1 million times smaller than a millimeter = 1 nanometer, which is the length of 10 hydrogen atoms. I don't think you need that much accuracy. 7 decimal places = 10 millimeters which requires exactly 32 bits so this fits well. To give you idea of savings, if you encode with JSON string 14 decimal places will take up 21 bytes = 168 bits, if you encode 14 decimal places to binary with writeDoubleBE that will take up 8 bytes = 64 bits, and if you encode 7 decimal places binary that will be 4 bytes = 32 bits, which is 19% the size of the JSON encoding and 50% the size of the 14 decimal place in binary, so is good savings

i was trying to create a function or a class that will scan my object, create a schema and then pack everything, on client i will need to have that schema to unpack and recreate my object

That is fine, if you could address the 2 questions I had above I can finish the encode / decode functions, the estimate number of ints in each set and if 7 decimal places for coordinates can work for you

[Wyzix33]

o._id can be sent as blob if i can decode it to string, i just need it in case any object get edited and i have to update/remove it from db later.
o.type can be from 0 to 24
o.features.id from 0 to 99
o.features.type can be 0 to 200
o.features.geometry.type 0 or 1
and i just tested the coordinates limiting them to 7 decimals and it seems to be OK, so they can be from 2 to 7 decimals max

[e3dio]

Ok the below code does a full encode and decode of the dataset you gave above. It takes an array of objects and combines them into 1 buffer. You can change this around to how you want it to work. The only thing that makes this tricky is you have arrays of arrays of arrays embedded in each other, this is easy to code but it might take a second for you to read. You can run this code and it will print the same decoded data as the original data. Looks like this encode is averaging 5x smaller than the JSON equivalent, most of the size coming from coordinates. It assumes a max 65,536 items per each level array, you can adjust this as needed to reduce or increase size. This is to get you started, I assume you need to make adjustments for your case, and any scanning of data to adjust the encoding function is up to you. Send the decode.js function to the client and they can decode the data, for Browsers use DataView to read buffer

import { ObjectId } from 'mongodb';
import { packBytes, unpackBytes } from 'packBytes';

const data = [ {
    "_id" : ObjectId("6291ff2dee2b7aec3b7070a5"),
    "type" : "FeatureCollection",
    "features" : [ {
        "id" : "BE",
        "type" : "Feature",
        "geometry" : {
            "type" : "MultiPolygon",
            "coordinates" : [
                [
                    [
                        [ 6.01991571473328, 50.7536455777936], 
                        [ 6.00146432981927, 50.7529502929202], 
                        [ 5.98266589691314, 50.7524013765143], 
                    ]
                ],
                [
                    [
                        [ 4.925853, 51.442709 ], 
                        [ 4.923032, 51.447411 ], 
                        [ 4.917302, 51.435413 ], 
                        [ 4.939683, 51.430785 ], 
                        [ 4.938087, 51.444699 ], 
                        [ 4.925853, 51.442709 ],
                   ]
                ]
            ]
        },
    } ]
} ];

const encodeLat = float => (float + 90) * 1e7;
const encodeLon = float => (float + 180) * 1e7;
const decodeLat = int => int / 1e7 - 90;
const decodeLon = int => int / 1e7 - 180;

// string to integer maps
const encodeType = str => ({ 'FeatureCollection': 24 })[str];
const encodeFeaturesId = str => ({ 'BE': 99 })[str];
const encodeFeaturesType = str => ({ 'Feature': 200 })[str];
const encodeFeaturesGeoType = str => ({ 'MultiPolygon': 1})[str];

// integer to string maps
const decodeType = int => ({ 24: 'FeatureCollection' })[int];
const decodeFeaturesId = int => ({ 99: 'BE' })[int];
const decodeFeaturesType = int => ({ 200: 'Feature' })[int];
const decodeFeaturesGeoType = int => ({ 1: 'MultiPolygon'})[int];

const encode = (data) => {

    // get total bytes needed for buffer
    let bufferSize = 0;
    data.forEach(obj => {
        bufferSize += 12 + 4 + 2; // 12 byte ObjectID, 4 byte packBytes, 2 byte array length
        obj.features[0].geometry.coordinates.forEach(polygon => {
            bufferSize += 2; // 2 byte array length
            polygon.forEach(path => {
                bufferSize += 2 + path.length * 8; // 2 byte array length, 8 bytes per coord pair
            });
        });
    });

    const buf = Buffer.allocUnsafe(bufferSize);
    let offset = 0;

    data.forEach(d => {
        d._id.id.copy(buf, offset); // copy ObjectID buffer = 12 bytes
        offset += 12;

        buf.writeUInt32BE(packBytes(
            5, encodeType(d.type),
            7, encodeFeaturesId(d.features[0].id),
            8, encodeFeaturesType(d.features[0].type),
            1, encodeFeaturesGeoType(d.features[0].geometry.type),
        ), offset); // type, features.id, features.type, features.geometry.type = 4 bytes
        offset += 4;

        buf.writeUInt16BE(d.features[0].geometry.coordinates.length, offset); // features.geometry.coordinates.length = 2 bytes
        offset += 2;

        d.features[0].geometry.coordinates.forEach(paths => {
            buf.writeUInt16BE(paths.length, offset); // features.geometry.coordinates.innerArray.length = 2 bytes
            offset += 2;

            paths.forEach(coords => {
                buf.writeUInt16BE(coords.length, offset); // features.geometry.coordinates.innerArray.length = 2 bytes
                offset += 2;

                coords.forEach(coordPair => {
                    buf.writeUInt32BE(encodeLat(coordPair[0]), offset); // lat = 4 bytes
                    buf.writeUInt32BE(encodeLon(coordPair[1]), offset + 4); // lon = 4 bytes
                    offset += 8;
                });
            });
        });
    });

    return buf;
};


const decode = (buf) => {

    const data = [];

    let offset = 0;
    while (offset < buf.length) {

        const obj = { };

        obj._id = new ObjectId(buf.subarray(offset, offset + 12));
        offset += 12;

        const [ type, featuresID, featuresType, featuresGeoType ] = unpackBytes(buf.readUInt32BE(offset), 5, 7, 8, 1);
        obj.type = decodeType(type);
        obj.features = [ {
            id: decodeFeaturesId(featuresID),
            type: decodeFeaturesType(featuresType),
            geometry: {
                type: decodeFeaturesGeoType(featuresGeoType),
                coordinates: []
            }
        } ];
        offset += 4;

        let numPolygons = buf.readUInt16BE(offset);
        offset += 2;

        while (numPolygons--) {
            const paths = [];
            let numPaths = buf.readUInt16BE(offset);
            offset += 2;

            while (numPaths--) {
                const coords = [];
                let numCoords = buf.readUInt16BE(offset);
                offset += 2;

                while (numCoords--) {
                    coords.push([ decodeLat(buf.readUInt32BE(offset)), decodeLon(buf.readUInt32BE(offset + 4)) ]);
                    offset += 8;
                }
                paths.push(coords);
            }
            obj.features[0].geometry.coordinates.push(paths);
        }

        data.push(obj);
    }

    return data;
};

const buf = encode(data);

const decodedData = decode(buf);

console.log(JSON.stringify(decodedData));

[Wyzix33]

Beautiful...
Thank you so much, it's a great improvement both in encoding/decoding speed and size.
It's enough to get me started.

[Wyzix33]

Can you also give me a simple example on how to handle a string property of unknown length?
I need to add another property with a small description after _id to this object.
Thanks

[e3dio]

const strLength = Buffer.byteLength(str);

// for max 255 length str
buf.writeUInt8(strLength, offset);
offset += 1;

// for max 65,535 length str
buf.writeUInt16BE(strLength, offset);
offset += 2;

buf.write(str, offset);
offset += strLength;

[Wyzix33]

It's working, for decoding i did this

  const strLength = buf.readUInt16BE(offset);
  offset += 2;
  obj.string = buf.toString('utf-8', offset, offset + strLength);
  offset += strLength;

Thanks