tests/varint-tests.lisp

   1 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   2 ;;;                                                                  ;;;
   3 ;;; Free Software published under an MIT-like license. See LICENSE   ;;;
   4 ;;;                                                                  ;;;
   5 ;;; Copyright (c) 2012 Google, Inc.  All rights reserved.            ;;;
   6 ;;;                                                                  ;;;
   7 ;;; Original author: Scott McKay                                     ;;;
   8 ;;; Based on original work by Robert Brown                           ;;;
   9 ;;;                                                                  ;;;
  10 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  11
  12 (in-package "PROTO-TEST")
  13
  14
  15 ;;; Varint unit tests
  16
  17 (define-test length32-test ()
  18   (assert-equal (length32 0) 1)
  19   (assert-equal (length32 1) 1)
  20   (assert-equal (length32 127) 1)
  21   (assert-equal (length32 128) 2)
  22   (assert-equal (length32 16383) 2)
  23   (assert-equal (length32 16384) 3)
  24   (assert-equal (length32 (ash 1 31)) 5))
  25
  26 (define-test length64-test ()
  27   (assert-equal (length64 0) 1)
  28   (assert-equal (length64 1) 1)
  29   (assert-equal (length64 127) 1)
  30   (assert-equal (length64 128) 2)
  31   (assert-equal (length64 16383) 2)
  32   (assert-equal (length64 16384) 3)
  33   (assert-equal (length64 (- (ash 1 21) 1)) 3)
  34   (assert-equal (length64 (ash 1 21)) 4)
  35   (assert-equal (length64 (ash 1 63)) 10))
  36
  37
  38 (define-test uint32-test ()
  39   (let* ((val #xE499867)
  40          (encoding #(#xE7 #xB0 #xA6 #x72))
  41          (len (length encoding))
  42          (buf (make-byte-vector len)))
  43     (let ((idx (encode-uint32 val buf 0)))
  44       (assert-equal idx len)
  45       (assert-true (equalp buf encoding))
  46       (multiple-value-bind (nval nidx)
  47           (decode-uint32 buf 0)
  48         (assert-equal nidx len)
  49         (assert-equal nval val)))))
  50
  51 (define-test uint64-test ()
  52   (let* ((val #xE4998679470D98D)
  53          (encoding #(#x8D #xB3 #xC3 #xA3 #xF9 #x8C #xE6 #xA4 #x0E))
  54          (len (length encoding))
  55          (buf (make-byte-vector len)))
  56     (let ((idx (encode-uint64 val buf 0)))
  57       (assert-equal idx len)
  58       (assert-true (equalp buf encoding))
  59       (multiple-value-bind (nval nidx)
  60           (decode-uint64 buf 0)
  61         (assert-equal nidx len)
  62         (assert-equal nval val)))))
  63
  64
  65 (defvar $max-bytes-32  5)
  66 (defvar $max-bytes-64 10)
  67
  68 (define-test powers-varint-test ()
  69   (let ((buffer (make-byte-vector (* 128 $max-bytes-64)))
  70         (index 0)
  71         length)
  72     ;; Encode powers of 2
  73     ;; Smaller powers are encoded as both 32-bit and 64-bit varints
  74     (dotimes (p 64)
  75       (when (< p 32)
  76         (setq index (encode-uint32 (ash 1 p) buffer index)))
  77       (setq index (encode-uint64 (ash 1 p) buffer index)))
  78     (setq length index)
  79
  80     ;; Test the decodings
  81     (setq index 0)
  82     (dotimes (p 64)
  83       (when (< p 32)
  84         (multiple-value-bind (val idx)
  85             (decode-uint32 buffer index)
  86           (assert-equal val (ash 1 p))
  87           (setq index idx)))
  88       (multiple-value-bind (val idx)
  89           (decode-uint64 buffer index)
  90         (assert-equal val (ash 1 p))
  91         (setq index idx)))
  92     (assert-equal index length)
  93
  94     ;; Test skipping, too
  95     (setq index 0)
  96     (dotimes (p 64)
  97       (when (< p 32)
  98         (setq index (skip-element buffer index $wire-type-varint)))
  99       (setq index (skip-element buffer index $wire-type-varint)))
 100     (assert-equal index length)))
 101
 102 (define-test random-varint-test ()
 103   ;; Encode 1000 random numbers as both 32-bit and 64-bit varints
 104   (let* ((count 1000)
 105          (buf32 (make-byte-vector (* count $max-bytes-32)))
 106          (buf64 (make-byte-vector (* count $max-bytes-64)))
 107          (vals32 (make-array count))
 108          (vals64 (make-array count))
 109          (index32 0)
 110          (index64 0))
 111     (dotimes (i count)
 112       (let* ((val64 (random (ash 1 64)))
 113              (val32 (ldb (byte 32 0) val64)))
 114         (setf (aref vals32 i) val32)
 115         (setf (aref vals64 i) val64)
 116         (setq index32 (encode-uint32 val32 buf32 index32))
 117         (setq index64 (encode-uint64 val64 buf64 index64))))
 118
 119     ;; Test the decodings
 120     (setq index32 0)
 121     (setq index64 0)
 122     (dotimes (i count)
 123       (multiple-value-bind (val32 idx)
 124           (decode-uint32 buf32 index32)
 125         (assert-equal val32 (aref vals32 i))
 126         (setq index32 idx))
 127       (multiple-value-bind (val64 idx)
 128           (decode-uint64 buf64 index64)
 129         (assert-equal val64 (aref vals64 i))
 130         (setq index64 idx)))))
 131
 132
 133 (define-test-suite varint-tests ()
 134   (length32-test
 135    length64-test
 136    uint32-test
 137    uint64-test
 138    powers-varint-test
 139    random-varint-test))
 140
 141 (register-test 'varint-tests)