| 1 | use crate::block::ClientID; |
| 2 | use crate::encoding::varint::Signed; |
| 3 | use crate::encoding::write::Write; |
| 4 | use crate::*; |
| 5 | use std::collections::HashMap; |
| 6 | |
| 7 | /// A trait that can be implemented by any other type in order to support lib0 encoding capability. |
| 8 | pub trait Encode { |
| 9 | fn encode<E: Encoder>(&self, encoder: &mut E); |
| 10 | |
| 11 | /// Helper function for encoding 1st version of lib0 encoding. |
| 12 | fn encode_v1(&self) -> Vec<u8> { |
| 13 | let mut encoder = EncoderV1::new(); |
| 14 | self.encode(&mut encoder); |
| 15 | encoder.to_vec() |
| 16 | } |
| 17 | |
| 18 | /// Helper function for encoding 2nd version of lib0 encoding. |
| 19 | fn encode_v2(&self) -> Vec<u8> { |
| 20 | let mut encoder = EncoderV2::new(); |
| 21 | self.encode(&mut encoder); |
| 22 | encoder.to_vec() |
| 23 | } |
| 24 | } |
| 25 | |
| 26 | /// Trait used by lib0 encoders. Natively lib0 encoding supports two versions: |
| 27 | /// |
| 28 | /// 1. 1st version (implemented in Yrs) uses simple optimization techniques like var int encoding. |
| 29 | /// 2. 2nd version optimizes bigger batches of blocks by using run-length encoding. |
| 30 | /// |
| 31 | /// Both of these define a common set of operations defined in this trait. |
| 32 | pub trait Encoder: Write { |
| 33 | /// Consume current encoder and return a binary with all data encoded so far. |
| 34 | fn to_vec(self) -> Vec<u8>; |
| 35 | |
| 36 | /// Reset the state of currently encoded [DeleteSet]. |
| 37 | fn reset_ds_cur_val(&mut self); |
| 38 | |
| 39 | /// Write a clock value of currently encoded [DeleteSet] client. |
| 40 | fn write_ds_clock(&mut self, clock: u32); |
| 41 | |
| 42 | /// Write a number of client entries used by currently encoded [DeleteSet]. |
| 43 | fn write_ds_len(&mut self, len: u32); |
| 44 | |
| 45 | /// Write unique identifier of a currently encoded [Block]'s left origin. |
| 46 | fn write_left_id(&mut self, id: &block::ID); |
| 47 | |
| 48 | /// Write unique identifier of a currently encoded [Block]'s right origin. |
| 49 | fn write_right_id(&mut self, id: &block::ID); |
| 50 | |
| 51 | /// Write currently encoded client identifier. |
| 52 | fn write_client(&mut self, client: ClientID); |
| 53 | |
| 54 | /// Write currently encoded [Block]'s info flags. These contain information about which fields |
| 55 | /// have been provided and which should be skipped during decoding process as well as a type of |
| 56 | /// block currently encoded. |
| 57 | fn write_info(&mut self, info: u8); |
| 58 | |
| 59 | /// Write info flag about currently encoded [Block]'s parent. Is is another block or root type. |
| 60 | fn write_parent_info(&mut self, is_y_key: bool); |
| 61 | |
| 62 | /// Writes type ref data of currently encoded [Block]'s parent. |
| 63 | fn write_type_ref(&mut self, info: u8); |
| 64 | |
| 65 | /// Write length parameter. |
| 66 | fn write_len(&mut self, len: u32); |
| 67 | |
| 68 | /// Encode JSON-like data type. This is a complex structure which is an extension to JavaScript |
| 69 | /// Object Notation with some extra cases. |
| 70 | fn write_any(&mut self, any: &Any); |
| 71 | |
| 72 | /// Encode JSON-like data type as nested JSON string. This is a complex structure which is an |
| 73 | /// extension to JavaScript Object Notation with some extra cases. |
| 74 | fn write_json(&mut self, any: &Any); |
| 75 | |
| 76 | /// Write a string key. |
| 77 | fn write_key(&mut self, string: &str); |
| 78 | } |
| 79 | |
| 80 | pub struct EncoderV1 { |
| 81 | buf: Vec<u8>, |
| 82 | } |
| 83 | |
| 84 | impl EncoderV1 { |
| 85 | pub fn new() -> Self { |
| 86 | EncoderV1 { |
| 87 | buf: Vec::with_capacity(1024), |
| 88 | } |
| 89 | } |
| 90 | |
| 91 | fn write_id(&mut self, id: &ID) { |
| 92 | self.write_var(id.client); |
| 93 | self.write_var(id.clock) |
| 94 | } |
| 95 | } |
| 96 | |
| 97 | impl Write for EncoderV1 { |
| 98 | #[inline] |
| 99 | fn write_all(&mut self, buf: &[u8]) { |
| 100 | self.buf.write_all(buf) |
| 101 | } |
| 102 | |
| 103 | #[inline] |
| 104 | fn write_u8(&mut self, value: u8) { |
| 105 | self.buf.write_u8(value) |
| 106 | } |
| 107 | } |
| 108 | |
| 109 | impl Encoder for EncoderV1 { |
| 110 | #[inline] |
| 111 | fn to_vec(self) -> Vec<u8> { |
| 112 | self.buf |
| 113 | } |
| 114 | |
| 115 | #[inline] |
| 116 | fn reset_ds_cur_val(&mut self) { |
| 117 | /* no op */ |
| 118 | } |
| 119 | |
| 120 | #[inline] |
| 121 | fn write_ds_clock(&mut self, clock: u32) { |
| 122 | self.write_var(clock) |
| 123 | } |
| 124 | |
| 125 | #[inline] |
| 126 | fn write_ds_len(&mut self, len: u32) { |
| 127 | self.write_var(len) |
| 128 | } |
| 129 | |
| 130 | #[inline] |
| 131 | fn write_left_id(&mut self, id: &ID) { |
| 132 | self.write_id(id) |
| 133 | } |
| 134 | |
| 135 | #[inline] |
| 136 | fn write_right_id(&mut self, id: &ID) { |
| 137 | self.write_id(id) |
| 138 | } |
| 139 | |
| 140 | #[inline] |
| 141 | fn write_client(&mut self, client: ClientID) { |
| 142 | self.write_var(client) |
| 143 | } |
| 144 | |
| 145 | #[inline] |
| 146 | fn write_info(&mut self, info: u8) { |
| 147 | self.write_u8(info) |
| 148 | } |
| 149 | |
| 150 | #[inline] |
| 151 | fn write_parent_info(&mut self, is_y_key: bool) { |
| 152 | self.write_var(if is_y_key { 1 as u32 } else { 0 as u32 }) |
| 153 | } |
| 154 | |
| 155 | #[inline] |
| 156 | fn write_type_ref(&mut self, info: u8) { |
| 157 | self.write_u8(info) |
| 158 | } |
| 159 | |
| 160 | #[inline] |
| 161 | fn write_len(&mut self, len: u32) { |
| 162 | self.write_var(len) |
| 163 | } |
| 164 | |
| 165 | #[inline] |
| 166 | fn write_any(&mut self, any: &Any) { |
| 167 | any.encode(self) |
| 168 | } |
| 169 | |
| 170 | fn write_json(&mut self, any: &Any) { |
| 171 | let mut buf = String::new(); |
| 172 | any.to_json(&mut buf); |
| 173 | self.write_string(buf.as_str()) |
| 174 | } |
| 175 | |
| 176 | #[inline] |
| 177 | fn write_key(&mut self, key: &str) { |
| 178 | self.write_string(key) |
| 179 | } |
| 180 | } |
| 181 | |
| 182 | pub struct EncoderV2 { |
| 183 | key_table: HashMap<String, u32>, |
| 184 | buf: Vec<u8>, |
| 185 | ds_curr_val: u32, |
| 186 | seqeuncer: u32, |
| 187 | key_clock_encoder: IntDiffOptRleEncoder, |
| 188 | client_encoder: UIntOptRleEncoder, |
| 189 | left_clock_encoder: IntDiffOptRleEncoder, |
| 190 | right_clock_encoder: IntDiffOptRleEncoder, |
| 191 | info_encoder: RleEncoder, |
| 192 | string_encoder: StringEncoder, |
| 193 | parent_info_encoder: RleEncoder, |
| 194 | type_ref_encoder: UIntOptRleEncoder, |
| 195 | len_encoder: UIntOptRleEncoder, |
| 196 | } |
| 197 | |
| 198 | impl EncoderV2 { |
| 199 | pub fn new() -> Self { |
| 200 | EncoderV2 { |
| 201 | key_table: HashMap::new(), |
| 202 | buf: Vec::new(), |
| 203 | seqeuncer: 0, |
| 204 | ds_curr_val: 0, |
| 205 | key_clock_encoder: IntDiffOptRleEncoder::new(), |
| 206 | client_encoder: UIntOptRleEncoder::new(), |
| 207 | left_clock_encoder: IntDiffOptRleEncoder::new(), |
| 208 | right_clock_encoder: IntDiffOptRleEncoder::new(), |
| 209 | info_encoder: RleEncoder::new(), |
| 210 | string_encoder: StringEncoder::new(), |
| 211 | parent_info_encoder: RleEncoder::new(), |
| 212 | type_ref_encoder: UIntOptRleEncoder::new(), |
| 213 | len_encoder: UIntOptRleEncoder::new(), |
| 214 | } |
| 215 | } |
| 216 | } |
| 217 | |
| 218 | impl Write for EncoderV2 { |
| 219 | #[inline] |
| 220 | fn write_all(&mut self, buf: &[u8]) { |
| 221 | self.buf.write_buf(buf) |
| 222 | } |
| 223 | |
| 224 | #[inline] |
| 225 | fn write_u8(&mut self, value: u8) { |
| 226 | self.buf.write_u8(value) |
| 227 | } |
| 228 | |
| 229 | #[inline] |
| 230 | fn write_string(&mut self, str: &str) { |
| 231 | self.string_encoder.write(str) |
| 232 | } |
| 233 | } |
| 234 | |
| 235 | impl Encoder for EncoderV2 { |
| 236 | fn to_vec(self) -> Vec<u8> { |
| 237 | let key_clock = self.key_clock_encoder.to_vec(); |
| 238 | let client = self.client_encoder.to_vec(); |
| 239 | let left_clock = self.left_clock_encoder.to_vec(); |
| 240 | let right_clock = self.right_clock_encoder.to_vec(); |
| 241 | let info = self.info_encoder.to_vec(); |
| 242 | let string = self.string_encoder.to_vec(); |
| 243 | let parent_info = self.parent_info_encoder.to_vec(); |
| 244 | let type_ref = self.type_ref_encoder.to_vec(); |
| 245 | let len = self.len_encoder.to_vec(); |
| 246 | let rest = self.buf; |
| 247 | let mut buf = Vec::new(); |
| 248 | buf.write_u8(0); // this is a feature flag that we might use in the future |
| 249 | buf.write_buf(key_clock); |
| 250 | buf.write_buf(client); |
| 251 | buf.write_buf(left_clock); |
| 252 | buf.write_buf(right_clock); |
| 253 | buf.write_buf(info); |
| 254 | buf.write_buf(string); |
| 255 | buf.write_buf(parent_info); |
| 256 | buf.write_buf(type_ref); |
| 257 | buf.write_buf(len); |
| 258 | buf.write_all(rest.as_slice()); |
| 259 | buf |
| 260 | } |
| 261 | |
| 262 | #[inline] |
| 263 | fn reset_ds_cur_val(&mut self) { |
| 264 | self.ds_curr_val = 0; |
| 265 | } |
| 266 | |
| 267 | fn write_ds_clock(&mut self, clock: u32) { |
| 268 | let diff = clock - self.ds_curr_val; |
| 269 | self.ds_curr_val = clock; |
| 270 | self.buf.write_var(diff) |
| 271 | } |
| 272 | |
| 273 | fn write_ds_len(&mut self, len: u32) { |
| 274 | debug_assert!(len != 0); |
| 275 | self.buf.write_var(len - 1); |
| 276 | self.ds_curr_val += len; |
| 277 | } |
| 278 | |
| 279 | fn write_left_id(&mut self, id: &ID) { |
| 280 | self.client_encoder.write_u64(id.client as u64); |
| 281 | self.left_clock_encoder.write_u32(id.clock) |
| 282 | } |
| 283 | |
| 284 | fn write_right_id(&mut self, id: &ID) { |
| 285 | self.client_encoder.write_u64(id.client as u64); |
| 286 | self.right_clock_encoder.write_u32(id.clock) |
| 287 | } |
| 288 | |
| 289 | #[inline] |
| 290 | fn write_client(&mut self, client: ClientID) { |
| 291 | self.client_encoder.write_u64(client as u64) |
| 292 | } |
| 293 | |
| 294 | #[inline] |
| 295 | fn write_info(&mut self, info: u8) { |
| 296 | self.info_encoder.write_u8(info) |
| 297 | } |
| 298 | |
| 299 | #[inline] |
| 300 | fn write_parent_info(&mut self, is_y_key: bool) { |
| 301 | self.parent_info_encoder |
| 302 | .write_u8(if is_y_key { 1 } else { 0 }) |
| 303 | } |
| 304 | |
| 305 | #[inline] |
| 306 | fn write_type_ref(&mut self, info: u8) { |
| 307 | self.type_ref_encoder.write_u64(info as u64) |
| 308 | } |
| 309 | |
| 310 | #[inline] |
| 311 | fn write_len(&mut self, len: u32) { |
| 312 | self.len_encoder.write_u64(len as u64); |
| 313 | } |
| 314 | |
| 315 | #[inline] |
| 316 | fn write_any(&mut self, any: &Any) { |
| 317 | let mut encoder = EncoderV1 { |
| 318 | buf: std::mem::take(&mut self.buf), |
| 319 | }; |
| 320 | any.encode(&mut encoder); |
| 321 | self.buf = encoder.buf; |
| 322 | } |
| 323 | |
| 324 | fn write_json(&mut self, any: &Any) { |
| 325 | self.write_any(any) |
| 326 | } |
| 327 | |
| 328 | fn write_key(&mut self, key: &str) { |
| 329 | //TODO: this is wrong (key_table is never updated), but this behavior matches Yjs |
| 330 | self.key_clock_encoder.write_u32(self.seqeuncer); |
| 331 | self.seqeuncer += 1; |
| 332 | if self.key_table.get(key).is_none() { |
| 333 | self.string_encoder.write(key); |
| 334 | } |
| 335 | } |
| 336 | } |
| 337 | |
| 338 | /// A combination of the IntDiffEncoder and the UintOptRleEncoder. |
| 339 | /// |
| 340 | /// The count approach is similar to the UintDiffOptRleEncoder, but instead of using the negative bitflag, it encodes |
| 341 | /// in the LSB whether a count is to be read. Therefore this Encoder only supports 31 bit integers! |
| 342 | /// |
| 343 | /// Encodes [1, 2, 3, 2] as [3, 1, 6, -1] (more specifically [(1 << 1) | 1, (3 << 0) | 0, -1]) |
| 344 | /// |
| 345 | /// Internally uses variable length encoding. Contrary to normal UintVar encoding, the first byte contains: |
| 346 | /// * 1 bit that denotes whether the next value is a count (LSB) |
| 347 | /// * 1 bit that denotes whether this value is negative (MSB - 1) |
| 348 | /// * 1 bit that denotes whether to continue reading the variable length integer (MSB) |
| 349 | /// |
| 350 | /// Therefore, only five bits remain to encode diff ranges. |
| 351 | /// |
| 352 | /// Use this Encoder only when appropriate. In most cases, this is probably a bad idea. |
| 353 | struct IntDiffOptRleEncoder { |
| 354 | buf: Vec<u8>, |
| 355 | last: u32, |
| 356 | count: u32, |
| 357 | diff: i32, |
| 358 | } |
| 359 | |
| 360 | impl IntDiffOptRleEncoder { |
| 361 | fn new() -> Self { |
| 362 | IntDiffOptRleEncoder { |
| 363 | buf: Vec::new(), |
| 364 | last: 0, |
| 365 | count: 0, |
| 366 | diff: 0, |
| 367 | } |
| 368 | } |
| 369 | |
| 370 | fn write_u32(&mut self, value: u32) { |
| 371 | let diff = value as i32 - self.last as i32; |
| 372 | if self.diff == diff { |
| 373 | self.last = value; |
| 374 | self.count += 1; |
| 375 | } else { |
| 376 | self.flush(); |
| 377 | self.count = 1; |
| 378 | self.diff = diff; |
| 379 | self.last = value; |
| 380 | } |
| 381 | } |
| 382 | |
| 383 | fn flush(&mut self) { |
| 384 | if self.count > 0 { |
| 385 | // 31 bit making up the diff | wether to write the counter |
| 386 | let encode_diff = self.diff << 1 | (if self.count == 1 { 0 } else { 1 }); |
| 387 | // flush counter, unless this is the first value (count = 0) |
| 388 | // case 1: just a single value. set first bit to positive |
| 389 | // case 2: write several values. set first bit to negative to indicate that there is a length coming |
| 390 | self.buf.write_var(encode_diff as i64); |
| 391 | if self.count > 1 { |
| 392 | self.buf.write_var(self.count - 2); |
| 393 | } |
| 394 | } |
| 395 | } |
| 396 | |
| 397 | fn to_vec(mut self) -> Vec<u8> { |
| 398 | self.flush(); |
| 399 | self.buf |
| 400 | } |
| 401 | } |
| 402 | |
| 403 | /// Optimized Rle encoder that does not suffer from the mentioned problem of the basic Rle encoder. |
| 404 | /// |
| 405 | /// Internally uses VarInt encoder to write unsigned integers. If the input occurs multiple times, we write |
| 406 | /// write it as a negative number. The UintOptRleDecoder then understands that it needs to read a count. |
| 407 | /// |
| 408 | /// Encodes [1,2,3,3,3] as [1,2,-3,3] (once 1, once 2, three times 3) |
| 409 | struct UIntOptRleEncoder { |
| 410 | buf: Vec<u8>, |
| 411 | last: u64, |
| 412 | count: u32, |
| 413 | } |
| 414 | |
| 415 | impl UIntOptRleEncoder { |
| 416 | fn new() -> Self { |
| 417 | UIntOptRleEncoder { |
| 418 | buf: Vec::new(), |
| 419 | last: 0, |
| 420 | count: 0, |
| 421 | } |
| 422 | } |
| 423 | |
| 424 | fn write_u64(&mut self, value: u64) { |
| 425 | if self.last == value { |
| 426 | self.count += 1; |
| 427 | } else { |
| 428 | self.flush(); |
| 429 | self.count = 1; |
| 430 | self.last = value; |
| 431 | } |
| 432 | } |
| 433 | |
| 434 | fn to_vec(mut self) -> Vec<u8> { |
| 435 | self.flush(); |
| 436 | self.buf |
| 437 | } |
| 438 | |
| 439 | fn flush(&mut self) { |
| 440 | if self.count > 0 { |
| 441 | // flush counter, unless this is the first value (count = 0) |
| 442 | // case 1: just a single value. set sign to positive |
| 443 | // case 2: write several values. set sign to negative to indicate that there is a length coming |
| 444 | if self.count == 1 { |
| 445 | self.buf.write_var(self.last as i64); |
| 446 | } else { |
| 447 | let value = Signed::new(-(self.last as i64), true); |
| 448 | self.buf.write_var_signed(&value); |
| 449 | self.buf.write_var(self.count - 2); |
| 450 | } |
| 451 | } |
| 452 | } |
| 453 | } |
| 454 | |
| 455 | /// Basic Run Length Encoder - a basic compression implementation. |
| 456 | /// |
| 457 | /// Encodes [1,1,1,7] to [1,3,7,1] (3 times 1, 1 time 7). This encoder might do more harm than good if there are a lot of values that are not repeated. |
| 458 | /// |
| 459 | /// It was originally used for image compression. Cool .. article http://csbruce.com/cbm/transactor/pdfs/trans_v7_i06.pdf |
| 460 | struct RleEncoder { |
| 461 | buf: Vec<u8>, |
| 462 | last: Option<u8>, |
| 463 | count: u32, |
| 464 | } |
| 465 | |
| 466 | impl RleEncoder { |
| 467 | fn new() -> Self { |
| 468 | RleEncoder { |
| 469 | buf: Vec::new(), |
| 470 | last: None, |
| 471 | count: 0, |
| 472 | } |
| 473 | } |
| 474 | |
| 475 | fn write_u8(&mut self, value: u8) { |
| 476 | if self.last == Some(value) { |
| 477 | self.count += 1; |
| 478 | } else { |
| 479 | if self.count > 0 { |
| 480 | // flush counter, unless this is the first value (count = 0) |
| 481 | self.buf.write_var(self.count - 1); |
| 482 | } |
| 483 | self.count = 1; |
| 484 | self.buf.write_u8(value); |
| 485 | self.last = Some(value); |
| 486 | } |
| 487 | } |
| 488 | |
| 489 | fn to_vec(self) -> Vec<u8> { |
| 490 | self.buf |
| 491 | } |
| 492 | } |
| 493 | |
| 494 | /// Optimized String Encoder. |
| 495 | /// |
| 496 | /// Encoding many small strings in a simple Encoder is not very efficient. The function call to decode a string takes some time and creates references that must be eventually deleted. |
| 497 | /// In practice, when decoding several million small strings, the GC will kick in more and more often to collect orphaned string objects (or maybe there is another reason?). |
| 498 | /// |
| 499 | /// This string encoder solves the above problem. All strings are concatenated and written as a single string using a single encoding call. |
| 500 | /// |
| 501 | /// The lengths are encoded using a UintOptRleEncoder. |
| 502 | struct StringEncoder { |
| 503 | buf: String, |
| 504 | len_encoder: UIntOptRleEncoder, |
| 505 | } |
| 506 | |
| 507 | impl StringEncoder { |
| 508 | fn new() -> Self { |
| 509 | StringEncoder { |
| 510 | buf: String::new(), |
| 511 | len_encoder: UIntOptRleEncoder::new(), |
| 512 | } |
| 513 | } |
| 514 | |
| 515 | fn write(&mut self, str: &str) { |
| 516 | let utf16_len = str.encode_utf16().count(); // Yjs encodes offsets using utf-16 |
| 517 | self.buf.push_str(str); |
| 518 | self.len_encoder.write_u64(utf16_len as u64); |
| 519 | } |
| 520 | |
| 521 | fn to_vec(self) -> Vec<u8> { |
| 522 | let lengths = self.len_encoder.to_vec(); |
| 523 | let mut buf = Vec::with_capacity(self.buf.len() + lengths.len()); |
| 524 | buf.write_string(&self.buf); |
| 525 | buf.write_all(lengths.as_slice()); |
| 526 | buf |
| 527 | } |
| 528 | } |
| 529 | |
amadan