• Stars
    star
    264
  • Rank 154,535 (Top 4 %)
  • Language
    Rust
  • License
    Apache License 2.0
  • Created about 5 years ago
  • Updated over 2 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

dipa makes it easy to efficiently delta encode large Rust data structures.

dipa Actions Status docs

dipa makes it easy to efficiently delta encode large Rust data structures.

In some applications, the data that you are sending to the client is often almost exactly the same as the data that you last sent to them.

Rather than repeatedly sending nearly identical state objects to a client, an application might calculate what has changed since the last time data was sent and then only send down those changes.

This approach can dramatically reduce both your and your users' bandwidth requirements and network traffic costs.

The process of determining what has changed between two instances of a data structure is known as delta encoding.

Historically, delta encoding code would become more and more difficult to maintain as your application's data structures grew more and more complex.

This made it a tedious optimization reserved for only the most bandwidth sensitive applications, such as networked games.

dipa eliminates the maintainability challenges of efficient delta encoding code by generating all of the code for you.

dipa is designed to generate very tiny diffs by default. In the most sensitive cases where you have application specific knowledge about your data structures that could help you generate even tinier diffs, you can implement the traits for that type yourself and let dipa's derive macro take care of the rest.

Note that dipa does not know anything about networks and has no networking code. It is only focused on encoding deltas, not transmitting them.

The dipa Book

The dipa Book will introduce you to the library and teach you how to use it.

It is also available offline:

# Do this once while online
git clone [email protected]:chinedufn/dipa.git && cd dipa
cargo install mdbook

# This works offline
./bin/serve-book.sh

Quickstart

The easiest way to get started with dipa is by using the #[derive(DiffPatch)] macro. Here's a quick peek.

Click to show Cargo.toml.
[dependencies]

bincode = "1"
dipa = { version = "0.1", features = ["derive"] }
serde = { version = "1", features = ["derive"] }

use dipa::{DiffPatch};
use std::borrow::Cow;

#[derive(DiffPatch)]
struct MyClientState {
    id: u32,
    friends: Option<u8>,
    position: Position,
    notifications: Vec<Cow<&'static, str>>,
    emotional_state: EmotionalState
}

#[derive(DiffPatch)]
struct Position {
    x: f32,
    y: f32,
    z: f32
}

#[derive(DiffPatch)]
enum EmotionalState {
    Peace { calibration: u128 },
    Love(u64),
    Courage(u32),
}

fn main() {
    let mut old_client_state = MyClientState {
        id: 308,
        friends: None,
        position: Position { x: 1., y: 2., z: 3. }
        notifications: vec![Cow::Borrowed("let"), Cow::Owned("go".to_string())],
        emotional_state: EmotionalState::Love(100),
    };

    let new_client_state = MyClientState {
        id: 308,
        friends: Some(1),
        position: Position { x: 4., y: 2., z: 3. }
        notifications: vec![Cow::Borrowed("free")]
        emotional_state: EmotionalState::Peace { calibration: 10_000 },
    };

    let delta_created = old_client_state.create_delta_towards(&new_client_state);

    // Consider using bincode to serialize your diffs on the server side.
    // You can then send them over the wire and deserialize them on the client side.
    //
    // For the tiniest diffs, be sure to use variable integer encoding.
    let bin = bincode::options().with_varint_encoding();

    let serialized = bin.serialize(&delta_created.delta).unwrap();

    // ... Pretend you send the data to the client ...

    let deserialized: <MyClientState as dipa::Diffable<'_, '_, MyClientState>>::DeltaOwned = 
        bin.deserialize(&serialized).unwrap();

    old_client_state.apply_patch(deserialized);

    // All of the fields are now equal.
    assert_eq!(
      old_client_state.notifications,
      new_client_state.notifications
    );
}

See the full API Documentation

Advanced Usage

For applications where incredibly small payloads are a top priority, you may wish to take advantage of knowledge about how your application works in order to generate even smaller diffs.

For example, say you have the following client state data structure.

#[derive(DiffPatch)]
struct ClientState {
    hair_length: u128
}

If the hair length hasn't changed the diff will be a single byte.

However, whenever the client's hair length changes there will be up to an additional 17* bytes in the payload to variable integer encode the new u128 value.

But, what if you knew that it was impossible for a client's hair length to ever change by more than 100 units in between state updates?

And, your application requirements mean that saving every byte matters and so it is worth your time to customize your hair length delta encoding.

In this case, you could go for something like:

use dipa::{CreatedDelta, Diffable, Patchable};

#[derive(DiffPatch)]
// Debug + PartialEq are used by DipaImplTester below.
// They are not required otherwise.
#[cfg_attr(test, derive(Debug, PartialEq))]
struct ClientState {
    hair_length: DeltaWithI8,
}

// Debug + PartialEq are used by DipaImplTester below.
// They are not required otherwise.
#[cfg_attr(test, derive(Debug, PartialEq))]
struct DeltaWithI8(u128);

impl<'s, 'e> Diffable<'s, 'e, DeltaWithI8> for DeltaWithI8 {
    type Delta = i8;
    type DeltaOwned = Self::Delta;

    fn create_delta_towards(&self, end_state: &Self) -> CreatedDelta<Self::Delta> {
        let delta = if self.0 >= end_state.0 {
            (self.0 - end_state.0) as i8 * -1
        } else {
            (end_state.0 - self.0) as i8
        };

        CreatedDelta {
            delta,
            did_change: self.0 != end_state.0,
        }
    }
}

impl Patchable<i8> for DeltaWithI8 {
    fn apply_patch(&mut self, patch: i8) {
        if patch >= 0 {
            self.0 += patch as u128;
        } else {
            self.0 -= (-1 * patch) as u128;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use dipa::DipaImplTester;

    #[test]
    fn delta_with_i8() {
        DipaImplTester {
            label: Some("Unchanged DeltaWithI8"),
            start: &mut DeltaWithI8(300),
            end: &DeltaWithI8(300),
            expected_delta: 0,
            expected_serialized_patch_size: 1,
            expected_did_change: false,
        }
        .test();

        DipaImplTester {
            label: Some("Increase DeltaWithI8"),
            start: &mut DeltaWithI8(5_000),
            end: &DeltaWithI8(5_050),
            expected_delta: 50,
            expected_serialized_patch_size: 1,
            expected_did_change: true,
        }
        .test();

        DipaImplTester {
            label: Some("Decrease DeltaWithI8"),
            start: &mut DeltaWithI8(400),
            end: &DeltaWithI8(320),
            expected_delta: -80,
            expected_serialized_patch_size: 1,
            expected_did_change: true,
        }
        .test();
    }
}

This approach would reduce hair length delta from 17 bytes down to just a single byte.

* - 17, not 16, since integers larger than u8/i8 are wrapped in Option by their default DiffPatch implementation. This optimizes for the case when the integer does not change since None serializes to 1 byte.

Questions

If you have a question that you can't find the answer to within five minutes then this is considered a documentation bug.

Please open an issue with your question.

Or, even better, a work-in-progress pull request with a skeleton of a code example, API documentation or area in the book where your question could have been answered.

Contributing

If you have a use case that isn't supported, a question, a patch, or anything else, go right ahead and open an issue or submit a pull request.

To Test

To run the test suite.

# Clone the repository
git clone [email protected]:chinedufn/dipa.git
cd dipa

# Run tests
cargo test --all

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this project by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

More Repositories

1

percy

Build frontend browser apps with Rust + WebAssembly. Supports server side rendering.
Rust
2,260
star
2

swift-bridge

swift-bridge facilitates Rust and Swift interop.
Rust
800
star
3

webgl-water-tutorial

The source code for a tutorial on rendering water using WebGL + Rust + WebAssembly
Rust
477
star
4

psd

A Rust API for parsing and working with PSD files.
Rust
265
star
5

skeletal-animation-system

A standalone, stateless, dual quaternion based skeletal animation system built with interactive applications in mind
JavaScript
250
star
6

landon

A collection of tools, data structures and methods for exporting Blender data (such as meshes and armatures) and preparing it for your rendering pipeline.
Rust
147
star
7

collada-dae-parser

Parse collada .dae 3d animation files into a WebGL friendly JSON format
JavaScript
103
star
8

cross-compile-rust-from-mac-to-linux

An example of how to cross compile Rust from `macOS` to Linux `x86_64-unknown-linux-gnu`
Shell
95
star
9

rectangle-pack

A general purpose, deterministic bin packer designed to conform to any two or three dimensional use case.
Rust
72
star
10

blender-iks-to-fks

A Blender script that takes a mesh and armature that use IKs and other non-deformation bones and creates a new mesh and armature that uses only FK bones.
Python
44
star
11

hot-app-replacement

Like hot module replacement but... yeah you'll see
JavaScript
26
star
12

blender-webgl-hot-reload-experiment

An experiment in hot reloading 3d models from Blender into a WebGL scene
JavaScript
23
star
13

blender-actions-to-json

Write the joint data for all of a `.blend` file's actions to a JSON file
Python
17
star
14

webgl-particle-effect-tutorial

A tutorial for creating a WebGL fire particle effect using billboarded quads
JavaScript
17
star
15

wavefront-obj-parser

An api and cli for parsing wavefront .obj files into JSON
JavaScript
17
star
16

webgl-shadow-mapping-tutorial

A WebGL shadow mapping tutorial
JavaScript
16
star
17

mat4-to-dual-quat

Convert a 4x4 matrix into a dual quaternion. Useful for skeletal animation (dual quaternion linear blending)
JavaScript
14
star
18

virtual-progress-bar

virtual-dom progress bar component
JavaScript
11
star
19

virtual-loading-dots

virtual-dom loading dots component
JavaScript
9
star
20

webgl-skeletal-animation-tutorial

A quick tutorial on WebGL skeletal animation using small modules
JavaScript
9
star
21

watertight-ray-triangle-intersection

An implementation of the Watertight Ray/Triangle Intersection algorithm
JavaScript
9
star
22

solid-state

Trigger listener functions when your state changes
JavaScript
8
star
23

blender-webgl-skinned-hot-reload-experiment

An experiment in hot reloading skinned models from Blender to WebGL
JavaScript
7
star
24

dom-filenameify

Add filenames as attributes to your DOM elements to help locate them in code by inspect-elementing them in the browser
JavaScript
7
star
25

webgl-unit-test-tutorial

The source code for a tutorial on unit testing WebGL components
JavaScript
7
star
26

image-to-heightmap

Convert a JPG or PNG image into a heightmap array
JavaScript
7
star
27

webgl-wield-item-tutorial

A tutorial for positioning items on top of bones using WebGL and 3d math
JavaScript
6
star
28

create-keyframe

Create css keyframes using JSON
JavaScript
6
star
29

webgl-to-img-stream

Use a WebGL context to write the canvas's contents to a image file. Meant to be used in Node.js
JavaScript
5
star
30

load-collada-dae

Load the WebGL graphics buffer data from a collada .dae model and return a draw command that accepts options
JavaScript
5
star
31

app-world

A framework agnostic approach to managing frontend application state.
Rust
5
star
32

make-component

A code generator for virtual-dom component files
JavaScript
3
star
33

client-ketchup

A simple interface for keeping remote clients up to date with their authoritative state
JavaScript
3
star
34

neighborhood-pathfinder

An A* implementation that accepts a function to detect neighboring tiles
JavaScript
3
star
35

webgl-skeletal-animation-sound-tutorial

A tutorial for playing sound effects during skeletal animations
JavaScript
2
star
36

expand-vertex-data

Expand vertex, normal and uv indices into vertex normal and uv data that is ready for your array buffers
JavaScript
2
star
37

minimal-object-diff

Create and apply a tiny representation of diffs between two objects. Useful for sending diffs over a network
JavaScript
2
star
38

generate-keyframe-animation-tutorial

A tutorial on generating CSS keyframes during runtime
JavaScript
2
star
39

branching-dialogue

A stateless API for modeling branching dialogue in role-playing games
JavaScript
2
star
40

conformer

conformer helps you write and visualize conformance test suites.
Rust
2
star
41

create-hover-class

Turn a JSON object into :hover class to use with inline styled components
JavaScript
2
star
42

load-wavefront-obj

Load the graphics buffer data from a wavefront .obj model and return a draw command that accepts options
JavaScript
2
star
43

get-attributes-uniforms

Get the attributes and uniforms from a GLSL shader string
JavaScript
2
star
44

keyframes-to-dual-quats

Convert a set of keyframe matrices into dual quaternions
JavaScript
1
star
45

knowledge

Concepts, solutions and links that I want to remember
1
star
46

angular-video-time

AngularJS Filter for displaying a video's current time
JavaScript
1
star
47

create-shader-program

Compiles, links and returns a shader program from a give vertex and fragment shader
JavaScript
1
star
48

webgl-blend-map-tutorial

A tutorial on multitexturing a WebGL terrain using a blend map
JavaScript
1
star
49

epoch-to-timeago

Get a string representation of a time difference
JavaScript
1
star
50

create-orbit-camera

Create a camera that orbits a target
JavaScript
1
star
51

blender-rustlang-docker

Docker image with Blender 2.80 and Rust
Dockerfile
1
star
52

create-draw-function

Create a WebGL draw call based on user provided data
JavaScript
1
star
53

donutjs-skeletal-animation-slides

Skeletal Animation in Your Browser via WebGL - the accompanying slides for a talk at Portland's Donut.js meetup
JavaScript
1
star