1use alloc::{borrow::Cow, string::String, vec::Vec};
2
3use crate::{
4 canonical::encode_varint_le, BitReader, BitWriter, Config, Error, Result, TrailingBytes,
5};
6
7const RAW_UTF8: u8 = 0;
8const ASCII7: u8 = 1;
9const RAW_INTEGERS: u8 = 0;
10const DELTA_INTEGERS: u8 = 1;
11const RLE_INTEGERS: u8 = 2;
12
13pub const HEURISTIC_SAMPLE: usize = 64;
16
17#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
23pub enum AdaptiveMode {
24 #[default]
30 Off,
31 Heuristic,
39 Exact,
43}
44
45#[derive(Clone, Copy, Debug, Eq, PartialEq)]
47pub enum StringStrategy {
48 RawUtf8,
50 Ascii7,
52}
53
54#[derive(Clone, Copy, Debug, Eq, PartialEq)]
56pub enum CollectionStrategy {
57 Raw,
59 Delta,
61 RunLength,
63}
64
65#[derive(Clone, Copy, Debug, Eq, PartialEq)]
67pub struct AdaptiveConfig {
68 base: Config,
69 mode: AdaptiveMode,
70}
71
72impl AdaptiveConfig {
73 pub(crate) const fn new(base: Config) -> Self {
74 Self {
75 base,
76 mode: AdaptiveMode::Off,
77 }
78 }
79
80 pub const fn base_config(self) -> Config {
82 self.base
83 }
84
85 pub const fn with_adaptive_mode(mut self, mode: AdaptiveMode) -> Self {
91 self.mode = mode;
92 self
93 }
94
95 pub const fn mode(self) -> AdaptiveMode {
97 self.mode
98 }
99
100 pub fn serialize<T: nextjson::NsonSerialize + ?Sized>(self, value: &T) -> Result<Vec<u8>> {
102 self.base.serialize(value)
103 }
104
105 pub fn deserialize<'de, T: nextjson::NsonDeserialize<'de>>(
107 self,
108 input: &'de [u8],
109 ) -> Result<T> {
110 self.base.deserialize(input)
111 }
112
113 pub fn encode_string(self, value: &str) -> Result<Vec<u8>> {
115 if self.mode == AdaptiveMode::Off {
116 let required = 1usize
118 .checked_add(varint_size(value.len() as u128))
119 .and_then(|size| size.checked_add(value.len()))
120 .ok_or(Error::Adaptive("encoded size overflow"))?;
121 self.enforce_byte_limit(required)?;
122 let mut output = Vec::with_capacity(required);
123 output.push(RAW_UTF8);
124 push_varint(&mut output, value.len() as u128);
125 output.extend_from_slice(value.as_bytes());
126 return Ok(output);
127 }
128 let required = self.encoded_string_size(value)?;
129 let mut output = Vec::new();
130 output
131 .try_reserve_exact(required)
132 .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
133 output.resize(required, 0);
134 self.encode_string_into_slice(&mut output, value)?;
135 Ok(output)
136 }
137
138 pub fn encoded_string_size(self, value: &str) -> Result<usize> {
140 let (_, _, required) = string_layout(value, self.mode)?;
141 self.enforce_byte_limit(required)?;
142 Ok(required)
143 }
144
145 pub fn encode_string_into_slice(self, output: &mut [u8], value: &str) -> Result<usize> {
149 let (strategy, payload_size, required) = string_layout(value, self.mode)?;
150 self.enforce_byte_limit(required)?;
151 if output.len() < required {
152 return Err(Error::BufferTooSmall {
153 required,
154 available: output.len(),
155 });
156 }
157 let mut cursor = OutputCursor::new(&mut output[..required]);
158 cursor.byte(match strategy {
159 StringStrategy::RawUtf8 => RAW_UTF8,
160 StringStrategy::Ascii7 => ASCII7,
161 });
162 cursor.varint(value.len() as u128);
163 match strategy {
164 StringStrategy::RawUtf8 => cursor.bytes(value.as_bytes()),
165 StringStrategy::Ascii7 => {
166 let packed = cursor.take_mut(payload_size);
167 let mut writer = BitWriter::new(packed);
168 for byte in value.bytes() {
169 writer.write(byte as u128, 7)?;
170 }
171 }
172 }
173 Ok(required)
174 }
175
176 pub fn string_strategy(self, input: &[u8]) -> Result<StringStrategy> {
178 match input.first().copied().ok_or(Error::UnexpectedEnd)? {
179 RAW_UTF8 => Ok(StringStrategy::RawUtf8),
180 ASCII7 => Ok(StringStrategy::Ascii7),
181 _ => Err(Error::Adaptive("unknown string strategy")),
182 }
183 }
184
185 pub fn decode_string(self, input: &[u8]) -> Result<String> {
187 Ok(self.decode_string_borrowed(input)?.into_owned())
188 }
189
190 pub fn decode_string_into_slice<'output>(
197 self,
198 output: &'output mut [u8],
199 input: &[u8],
200 ) -> Result<&'output str> {
201 self.enforce_byte_limit(input.len())?;
202 let mut cursor = Cursor::new(input);
203 let strategy = cursor.byte()?;
204 if !matches!(strategy, RAW_UTF8 | ASCII7) {
205 return Err(Error::Adaptive("unknown string strategy"));
206 }
207 let length = cursor.usize_varint()?;
208 if output.len() < length {
209 return Err(Error::BufferTooSmall {
210 required: length,
211 available: output.len(),
212 });
213 }
214
215 match strategy {
216 RAW_UTF8 => {
217 let bytes = cursor.take(length)?;
218 core::str::from_utf8(bytes).map_err(Error::InvalidUtf8)?;
219 output[..length].copy_from_slice(bytes);
220 }
221 ASCII7 => {
222 let meaningful_bits = length
223 .checked_mul(7)
224 .ok_or(Error::Adaptive("ASCII7 length overflow"))?;
225 let packed = meaningful_bits
226 .checked_add(7)
227 .ok_or(Error::Adaptive("ASCII7 length overflow"))?
228 / 8;
229 let bytes = cursor.take(packed)?;
230 let mut reader = BitReader::new(bytes);
231 for slot in &mut output[..length] {
232 *slot = reader.read(7)? as u8;
233 }
234 validate_ascii_padding(bytes, meaningful_bits)?;
235 }
236 _ => return Err(Error::Adaptive("unknown string strategy")),
237 }
238 cursor.finish(self.base.trailing)?;
239 core::str::from_utf8(&output[..length]).map_err(Error::InvalidUtf8)
240 }
241
242 pub fn decode_string_borrowed(self, input: &[u8]) -> Result<Cow<'_, str>> {
247 self.enforce_byte_limit(input.len())?;
248 let mut cursor = Cursor::new(input);
249 let strategy = cursor.byte()?;
250 let length = cursor.usize_varint()?;
251 let value = match strategy {
252 RAW_UTF8 => {
253 let bytes = cursor.take(length)?;
254 Cow::Borrowed(core::str::from_utf8(bytes).map_err(Error::InvalidUtf8)?)
255 }
256 ASCII7 => {
257 let meaningful_bits = length
258 .checked_mul(7)
259 .ok_or(Error::Adaptive("ASCII7 length overflow"))?;
260 let packed = meaningful_bits
261 .checked_add(7)
262 .ok_or(Error::Adaptive("ASCII7 length overflow"))?
263 / 8;
264 let bytes = cursor.take(packed)?;
265 let mut reader = BitReader::new(bytes);
266 let mut value = String::new();
267 value
268 .try_reserve_exact(length)
269 .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
270 for _ in 0..length {
271 value.push(reader.read(7)? as u8 as char);
274 }
275 validate_ascii_padding(bytes, meaningful_bits)?;
276 Cow::Owned(value)
277 }
278 _ => return Err(Error::Adaptive("unknown string strategy")),
279 };
280 cursor.finish(self.base.trailing)?;
281 Ok(value)
282 }
283
284 pub fn encode_i64_slice(self, values: &[i64]) -> Result<Vec<u8>> {
286 if self.mode == AdaptiveMode::Off {
287 self.enforce_collection_limit(values.len())?;
290 let mut output = Vec::with_capacity(values.len().saturating_add(1));
291 output.push(RAW_INTEGERS);
292 push_varint(&mut output, values.len() as u128);
293 for value in values {
294 push_varint(&mut output, zigzag_i64(*value));
295 }
296 self.enforce_byte_limit(output.len())?;
297 return Ok(output);
298 }
299 let required = self.encoded_i64_slice_size(values)?;
300 let mut output = Vec::new();
301 output
302 .try_reserve_exact(required)
303 .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
304 output.resize(required, 0);
305 self.encode_i64_slice_into_slice(&mut output, values)?;
306 Ok(output)
307 }
308
309 pub fn encoded_i64_slice_size(self, values: &[i64]) -> Result<usize> {
311 self.enforce_collection_limit(values.len())?;
312 let (_, _, required) = collection_layout(values, self.mode)?;
313 self.enforce_byte_limit(required)?;
314 Ok(required)
315 }
316
317 pub fn encode_i64_slice_into_slice(self, output: &mut [u8], values: &[i64]) -> Result<usize> {
321 self.enforce_collection_limit(values.len())?;
322 let (strategy, _, required) = collection_layout(values, self.mode)?;
323 self.enforce_byte_limit(required)?;
324 if output.len() < required {
325 return Err(Error::BufferTooSmall {
326 required,
327 available: output.len(),
328 });
329 }
330 let mut cursor = OutputCursor::new(&mut output[..required]);
331 cursor.byte(match strategy {
332 CollectionStrategy::Raw => RAW_INTEGERS,
333 CollectionStrategy::Delta => DELTA_INTEGERS,
334 CollectionStrategy::RunLength => RLE_INTEGERS,
335 });
336 cursor.varint(values.len() as u128);
337 match strategy {
338 CollectionStrategy::Raw => {
339 for value in values {
340 cursor.varint(zigzag_i64(*value));
341 }
342 }
343 CollectionStrategy::Delta => {
344 if let Some(first) = values.first() {
345 cursor.varint(zigzag_i64(*first));
346 for pair in values.windows(2) {
347 cursor.varint(zigzag_i128(pair[1] as i128 - pair[0] as i128));
348 }
349 }
350 }
351 CollectionStrategy::RunLength => {
352 let mut start = 0;
353 while start < values.len() {
354 let mut end = start + 1;
355 while end < values.len() && values[end] == values[start] {
356 end += 1;
357 }
358 cursor.varint(zigzag_i64(values[start]));
359 cursor.varint((end - start) as u128);
360 start = end;
361 }
362 }
363 }
364 Ok(required)
365 }
366
367 pub fn collection_strategy(self, input: &[u8]) -> Result<CollectionStrategy> {
369 match input.first().copied().ok_or(Error::UnexpectedEnd)? {
370 RAW_INTEGERS => Ok(CollectionStrategy::Raw),
371 DELTA_INTEGERS => Ok(CollectionStrategy::Delta),
372 RLE_INTEGERS => Ok(CollectionStrategy::RunLength),
373 _ => Err(Error::Adaptive("unknown collection strategy")),
374 }
375 }
376
377 pub fn decode_i64_vec(self, input: &[u8]) -> Result<Vec<i64>> {
379 let length = self.decoded_i64_slice_len(input)?;
380 let mut values = Vec::new();
381 values
382 .try_reserve_exact(length)
383 .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
384 values.resize(length, 0);
385 self.decode_i64_slice_into(&mut values, input)?;
386 Ok(values)
387 }
388
389 pub fn decoded_i64_slice_len(self, input: &[u8]) -> Result<usize> {
391 self.enforce_byte_limit(input.len())?;
392 let mut cursor = Cursor::new(input);
393 let strategy = cursor.byte()?;
394 if !matches!(strategy, RAW_INTEGERS | DELTA_INTEGERS | RLE_INTEGERS) {
395 return Err(Error::Adaptive("unknown collection strategy"));
396 }
397 let length = cursor.usize_varint()?;
398 self.enforce_collection_limit(length)?;
399 Ok(length)
400 }
401
402 pub fn decode_i64_slice_into(self, output: &mut [i64], input: &[u8]) -> Result<usize> {
407 self.enforce_byte_limit(input.len())?;
408 let mut cursor = Cursor::new(input);
409 let strategy = cursor.byte()?;
410 if !matches!(strategy, RAW_INTEGERS | DELTA_INTEGERS | RLE_INTEGERS) {
411 return Err(Error::Adaptive("unknown collection strategy"));
412 }
413 let length = cursor.usize_varint()?;
414 self.enforce_collection_limit(length)?;
415 if output.len() < length {
416 return Err(Error::BufferTooSmall {
417 required: length,
418 available: output.len(),
419 });
420 }
421 let mut written = 0usize;
422 match strategy {
423 RAW_INTEGERS => {
424 while written < length {
425 let remaining_values = length - written;
426 let plain = plain_varint_prefix(cursor.remaining_slice()).min(remaining_values);
427 for byte in cursor.take(plain)? {
428 output[written] = decode_i128(*byte as u128) as i64;
429 written += 1;
430 }
431 if written < length {
432 output[written] = decode_i64(cursor.varint()?)?;
433 written += 1;
434 }
435 }
436 }
437 DELTA_INTEGERS => {
438 if length != 0 {
439 output[0] = decode_i64(cursor.varint()?)?;
440 written = 1;
441 while written < length {
442 let delta = decode_i128(cursor.varint()?);
443 let next = (output[written - 1] as i128)
444 .checked_add(delta)
445 .and_then(|value| i64::try_from(value).ok())
446 .ok_or(Error::Adaptive("delta reconstruction overflow"))?;
447 output[written] = next;
448 written += 1;
449 }
450 }
451 }
452 RLE_INTEGERS => {
453 while written < length {
454 let value = decode_i64(cursor.varint()?)?;
455 let run = cursor.usize_varint()?;
456 if run == 0 || run > length - written {
457 return Err(Error::Adaptive("invalid run length"));
458 }
459 output[written..written + run].fill(value);
460 written += run;
461 }
462 }
463 _ => unreachable!("strategy was validated above"),
464 }
465 cursor.finish(self.base.trailing)?;
466 Ok(written)
467 }
468
469 fn enforce_byte_limit(self, length: usize) -> Result<()> {
470 if let Some(limit) = self.base.limit {
471 if length as u64 > limit {
472 return Err(Error::SizeLimit { limit });
473 }
474 }
475 Ok(())
476 }
477
478 fn enforce_collection_limit(self, length: usize) -> Result<()> {
479 if let Some(limit) = self.base.collection_limit {
480 if length as u64 > limit {
481 return Err(Error::CollectionLimit { limit });
482 }
483 }
484 Ok(())
485 }
486}
487
488fn validate_ascii_padding(bytes: &[u8], meaningful_bits: usize) -> Result<()> {
489 if meaningful_bits % 8 != 0
490 && bytes
491 .last()
492 .is_some_and(|last| last >> (meaningful_bits % 8) != 0)
493 {
494 return Err(Error::Adaptive("non-zero ASCII7 padding"));
495 }
496 Ok(())
497}
498
499fn string_layout(value: &str, mode: AdaptiveMode) -> Result<(StringStrategy, usize, usize)> {
500 let raw_size = value.len();
501 let packed_size = if mode == AdaptiveMode::Off {
504 None
505 } else if is_ascii(value.as_bytes()) {
506 Some(
507 value
508 .len()
509 .checked_mul(7)
510 .and_then(|bits| bits.checked_add(7))
511 .ok_or(Error::Adaptive("encoded size overflow"))?
512 / 8,
513 )
514 } else {
515 None
516 };
517 let (strategy, payload_size) = match packed_size {
518 Some(size) if size < raw_size => (StringStrategy::Ascii7, size),
519 _ => (StringStrategy::RawUtf8, raw_size),
520 };
521 let required = 1usize
522 .checked_add(varint_size(value.len() as u128))
523 .and_then(|size| size.checked_add(payload_size))
524 .ok_or(Error::Adaptive("encoded size overflow"))?;
525 Ok((strategy, payload_size, required))
526}
527
528fn is_ascii(input: &[u8]) -> bool {
529 #[cfg(feature = "simd")]
530 return crate::simd::is_ascii(input);
531 #[cfg(not(feature = "simd"))]
532 input.is_ascii()
533}
534
535fn plain_varint_prefix(input: &[u8]) -> usize {
536 #[cfg(feature = "simd")]
537 return crate::simd::plain_varint_prefix(input);
538 #[cfg(not(feature = "simd"))]
539 input.iter().take_while(|&&byte| byte <= 250).count()
540}
541
542fn raw_size(values: &[i64]) -> Result<usize> {
544 values.iter().try_fold(0usize, |size, value| {
545 size.checked_add(varint_size(zigzag_i64(*value)))
546 .ok_or(Error::Adaptive("encoded size overflow"))
547 })
548}
549
550fn delta_size(values: &[i64]) -> Result<usize> {
552 let Some(first) = values.first() else {
553 return Ok(0);
554 };
555 values
556 .windows(2)
557 .try_fold(varint_size(zigzag_i64(*first)), |size, pair| {
558 size.checked_add(varint_size(zigzag_i128(pair[1] as i128 - pair[0] as i128)))
559 .ok_or(Error::Adaptive("encoded size overflow"))
560 })
561}
562
563fn rle_size(values: &[i64]) -> Result<usize> {
565 let mut size = 0usize;
566 let mut start = 0;
567 while start < values.len() {
568 let mut end = start + 1;
569 while end < values.len() && values[end] == values[start] {
570 end += 1;
571 }
572 size = size
573 .checked_add(varint_size(zigzag_i64(values[start])))
574 .and_then(|size| size.checked_add(varint_size((end - start) as u128)))
575 .ok_or(Error::Adaptive("encoded size overflow"))?;
576 start = end;
577 }
578 Ok(size)
579}
580
581fn best_strategy(raw: usize, delta: usize, rle: usize) -> (CollectionStrategy, usize) {
583 if delta < raw && delta <= rle {
584 (CollectionStrategy::Delta, delta)
585 } else if rle < raw {
586 (CollectionStrategy::RunLength, rle)
587 } else {
588 (CollectionStrategy::Raw, raw)
589 }
590}
591
592fn collection_layout(
593 values: &[i64],
594 mode: AdaptiveMode,
595) -> Result<(CollectionStrategy, usize, usize)> {
596 let (strategy, payload_size) = match mode {
597 AdaptiveMode::Off => (CollectionStrategy::Raw, raw_size(values)?),
599 AdaptiveMode::Exact => {
601 let raw = raw_size(values)?;
602 let delta = delta_size(values)?;
603 let rle = rle_size(values)?;
604 best_strategy(raw, delta, rle)
605 }
606 AdaptiveMode::Heuristic if values.len() <= HEURISTIC_SAMPLE => {
608 let raw = raw_size(values)?;
609 let delta = delta_size(values)?;
610 let rle = rle_size(values)?;
611 best_strategy(raw, delta, rle)
612 }
613 AdaptiveMode::Heuristic => {
616 let sample = &values[..HEURISTIC_SAMPLE];
617 let raw = raw_size(sample)?;
618 let delta = delta_size(sample)?;
619 let rle = rle_size(sample)?;
620 let (chosen, _) = best_strategy(raw, delta, rle);
621 let payload = match chosen {
622 CollectionStrategy::Raw => raw_size(values)?,
623 CollectionStrategy::Delta => delta_size(values)?,
624 CollectionStrategy::RunLength => rle_size(values)?,
625 };
626 (chosen, payload)
627 }
628 };
629 let required = 1usize
630 .checked_add(varint_size(values.len() as u128))
631 .and_then(|size| size.checked_add(payload_size))
632 .ok_or(Error::Adaptive("encoded size overflow"))?;
633 Ok((strategy, payload_size, required))
634}
635
636const fn zigzag_i64(value: i64) -> u128 {
637 ((value << 1) ^ (value >> 63)) as u64 as u128
638}
639
640const fn zigzag_i128(value: i128) -> u128 {
641 ((value << 1) ^ (value >> 127)) as u128
642}
643
644fn decode_i64(value: u128) -> Result<i64> {
645 i64::try_from(decode_i128(value)).map_err(|_| Error::IntegerOverflow { target: "i64" })
646}
647
648const fn decode_i128(value: u128) -> i128 {
649 ((value >> 1) as i128) ^ -((value & 1) as i128)
650}
651
652const fn varint_size(value: u128) -> usize {
653 match value {
654 0..=250 => 1,
655 251..=0xffff => 3,
656 0x1_0000..=0xffff_ffff => 5,
657 0x1_0000_0000..=0xffff_ffff_ffff_ffff => 9,
658 _ => 17,
659 }
660}
661
662struct OutputCursor<'a> {
663 output: &'a mut [u8],
664 position: usize,
665}
666
667impl<'a> OutputCursor<'a> {
668 fn new(output: &'a mut [u8]) -> Self {
669 Self {
670 output,
671 position: 0,
672 }
673 }
674
675 fn byte(&mut self, value: u8) {
676 self.output[self.position] = value;
677 self.position += 1;
678 }
679
680 fn bytes(&mut self, value: &[u8]) {
681 self.take_mut(value.len()).copy_from_slice(value);
682 }
683
684 fn take_mut(&mut self, length: usize) -> &mut [u8] {
685 let start = self.position;
686 self.position += length;
687 &mut self.output[start..self.position]
688 }
689
690 fn varint(&mut self, value: u128) {
691 let (bytes, len) = encode_varint_le(value);
694 self.bytes(&bytes[..len]);
695 }
696}
697
698fn push_varint(output: &mut Vec<u8>, value: u128) {
703 let (bytes, len) = encode_varint_le(value);
704 output.extend_from_slice(&bytes[..len]);
705}
706
707struct Cursor<'a> {
708 input: &'a [u8],
709 position: usize,
710}
711
712impl<'a> Cursor<'a> {
713 const fn new(input: &'a [u8]) -> Self {
714 Self { input, position: 0 }
715 }
716
717 fn byte(&mut self) -> Result<u8> {
718 Ok(self.take(1)?[0])
719 }
720
721 fn take(&mut self, length: usize) -> Result<&'a [u8]> {
722 let end = self
723 .position
724 .checked_add(length)
725 .ok_or(Error::UnexpectedEnd)?;
726 let bytes = self
727 .input
728 .get(self.position..end)
729 .ok_or(Error::UnexpectedEnd)?;
730 self.position = end;
731 Ok(bytes)
732 }
733
734 fn remaining_slice(&self) -> &'a [u8] {
735 &self.input[self.position..]
736 }
737
738 fn take_array<const N: usize>(&mut self) -> Result<[u8; N]> {
739 self.take(N)?.try_into().map_err(|_| Error::UnexpectedEnd)
740 }
741
742 fn varint(&mut self) -> Result<u128> {
743 let marker = self.byte()?;
744 let (value, minimum) = match marker {
745 0..=250 => return Ok(marker as u128),
746 251 => (u16::from_le_bytes(self.take_array()?) as u128, 251),
747 252 => (u32::from_le_bytes(self.take_array()?) as u128, 0x1_0000),
748 253 => (
749 u64::from_le_bytes(self.take_array()?) as u128,
750 0x1_0000_0000,
751 ),
752 254 => (
753 u128::from_le_bytes(self.take_array()?),
754 0x1_0000_0000_0000_0000,
755 ),
756 marker => return Err(Error::InvalidVarintMarker(marker)),
757 };
758 if value < minimum {
759 Err(Error::NonCanonicalVarint)
760 } else {
761 Ok(value)
762 }
763 }
764
765 fn usize_varint(&mut self) -> Result<usize> {
766 usize::try_from(self.varint()?).map_err(|_| Error::IntegerOverflow { target: "usize" })
767 }
768
769 fn finish(self, trailing: TrailingBytes) -> Result<()> {
770 if trailing == TrailingBytes::Reject && self.position != self.input.len() {
771 return Err(Error::TrailingBytes {
772 remaining: self.input.len() - self.position,
773 });
774 }
775 Ok(())
776 }
777}