val lemma_big_endian_inj: b:word -> b':word {length b = length b'} -> Lemma
  (requires big_endian b = big_endian b')
  (ensures b == b')
  (decreases (length b))
let rec lemma_big_endian_inj s s' = 
  let len = length s in 
  if len = 0 then lemma_eq_intro s s'
  else
    let t = slice s 0 (len - 1) in 
    let x = last s in 
    lemma_eq_intro s (snoc t x);
    big_endian_step s;
    let t' = slice s' 0 (len - 1) in 
    let x' = last s' in 
    lemma_eq_intro s' (snoc t' x');
    big_endian_step s';
    endian_is_injective (big_endian t) x (big_endian t') x';
    lemma_big_endian_inj t t'
val lemma_big_endian_inj: b:word -> b':word {length b = length b'} -> Lemma
  (requires big_endian b = big_endian b')
  (ensures b == b')
  (decreases (length b))
let rec lemma_big_endian_inj s s' =
let len = length s in
if len = 0
then lemma_eq_intro s s'
else
  let t = slice s 0 (len - 1) in
  let x = last s in
  lemma_eq_intro s (snoc t x);
  big_endian_step s;
  let t' = slice s' 0 (len - 1) in
  let x' = last s' in
  lemma_eq_intro s' (snoc t' x');
  big_endian_step s';
  endian_is_injective (big_endian t) x (big_endian t') x';
  lemma_big_endian_inj t t'
FStar.Old.Endianness.fst.checked
prims.fst.checked FStar.UInt8.fsti.checked FStar.UInt64.fsti.checked FStar.UInt32.fsti.checked FStar.UInt128.fsti.checked FStar.Seq.fst.checked FStar.Pervasives.fsti.checked FStar.Mul.fst.checked FStar.Math.Lib.fst.checked FStar.Math.Lemmas.fst.checked FStar.Int.Cast.fst.checked FStar.HyperStack.ST.fsti.checked FStar.HyperStack.All.fst.checked FStar.Ghost.fsti.checked
FStar.Old.Endianness.fst
FStar.Old.Endianness.word Prims.b2t Prims.op_Equality Prims.nat FStar.Seq.Base.length FStar.UInt8.t Prims.int FStar.Seq.Base.lemma_eq_intro Prims.bool FStar.Old.Endianness.lemma_big_endian_inj Prims.unit FStar.Old.Endianness.endian_is_injective FStar.Old.Endianness.big_endian FStar.Old.Endianness.big_endian_step FStar.Seq.Properties.snoc FStar.Seq.Properties.last FStar.Seq.Base.seq FStar.Seq.Base.slice Prims.op_Subtraction
module FStar.Old.Endianness

module ST = FStar.HyperStack.ST

open FStar.HyperStack.All

open FStar.UInt32
open FStar.Ghost
open FStar.Mul
open FStar.Int.Cast

module U8 = FStar.UInt8

let u8  = UInt8.t
let u32 = UInt32.t
let u64 = UInt64.t

#set-options "--initial_fuel 0 --max_fuel 0"

type bytes  = Seq.seq U8.t // Pure sequence of bytes

type  lbytes  (l:nat) = b:bytes   {Seq.length b == l}

(* type lbuffer (l:nat) = b:buffer {Buffer.length b == l} *)

#reset-options

let uint128_to_uint8 (a:UInt128.t) : Tot (b:UInt8.t{UInt8.v b = UInt128.v a % pow2 8})
  = Math.Lemmas.pow2_modulo_modulo_lemma_2 (UInt128.v a) 64 8;
    uint64_to_uint8 (FStar.UInt128.uint128_to_uint64 a)

#reset-options "--z3rlimit 20 --initial_fuel 0 --max_fuel 0"


open FStar.Seq

(* Little endian integer value of a sequence of bytes *)
let rec little_endian (b:bytes) : Tot (n:nat) (decreases (Seq.length b)) =
  if Seq.length b = 0 then 0
  else
    UInt8.v (head b) + pow2 8 * little_endian (tail b)

(* Big endian integer value of a sequence of bytes *)
let rec big_endian (b:bytes) : Tot (n:nat) (decreases (Seq.length b)) = 
  if Seq.length b = 0 then 0 
  else
    UInt8.v (last b) + pow2 8 * big_endian (Seq.slice b 0 (Seq.length b - 1))

#reset-options "--initial_fuel 1 --max_fuel 1"

val little_endian_null: len:nat{len < 16} -> Lemma
  (little_endian (Seq.create len 0uy) == 0)
let rec little_endian_null len =
  if len = 0 then ()
  else
    begin
    Seq.lemma_eq_intro (Seq.slice (Seq.create len 0uy) 1 len)
		       (Seq.create (len - 1) 0uy);
    assert (little_endian (Seq.create len 0uy) ==
      0 + pow2 8 * little_endian (Seq.slice (Seq.create len 0uy) 1 len));
    little_endian_null (len - 1)
    end

val little_endian_singleton: n:UInt8.t -> Lemma
  (little_endian (Seq.create 1 n) == UInt8.v n)
let little_endian_singleton n =
  assert (little_endian (Seq.create 1 n) ==
    UInt8.v (Seq.index (Seq.create 1 n) 0) + pow2 8 *
    little_endian (Seq.slice (Seq.create 1 n) 1 1))


#reset-options "--initial_fuel 1 --max_fuel 1 --z3rlimit 50"

val little_endian_append: w1:bytes -> w2:bytes -> Lemma
  (requires True)
  (ensures
    little_endian (Seq.append w1 w2) ==
    little_endian w1 + pow2 (8 * Seq.length w1) * little_endian w2)
  (decreases (Seq.length w1))
let rec little_endian_append w1 w2 =
  let open FStar.Seq in
  if length w1 = 0 then
    begin
    assert_norm (pow2 (8 * 0) == 1);
    Seq.lemma_eq_intro (append w1 w2) w2
    end
  else
    begin
    let w1' = slice w1 1 (length w1) in
    assert (length w1' == length w1 - 1);
    little_endian_append w1' w2;
    assert (index (append w1 w2) 0 == index w1 0);
    Seq.lemma_eq_intro
      (append w1' w2)
      (Seq.slice (append w1 w2) 1 (length (append w1 w2)));
    assert (little_endian (append w1 w2) ==
      UInt8.v (index w1 0) + pow2 8 * little_endian (append w1' w2));
    assert (little_endian (append w1' w2) ==
      little_endian w1' + pow2 (8 * length w1') * little_endian w2);
    assert (UInt8.v (index w1 0) + pow2 8 * little_endian (append w1' w2) ==
      UInt8.v (index w1 0) +
      pow2 8 * (little_endian w1' + pow2 (8 * length w1') * little_endian w2));
    Math.Lemmas.pow2_plus 8 (8 * (length w1 - 1));
    assert (pow2 8 * pow2 (8 * length w1') == pow2 (8 * length w1));
    assert (UInt8.v (index w1 0) + pow2 8 * little_endian (append w1' w2) ==
      UInt8.v (index w1 0) +
      pow2 8 * little_endian w1' + pow2 (8 * length w1) * little_endian w2);
    assert (UInt8.v (index w1 0) + pow2 8 * little_endian w1' == little_endian w1)
    end


#reset-options "--initial_fuel 1 --max_fuel 1 --z3rlimit 50"

val lemma_euclidean_division: r:nat -> b:nat -> q:pos -> Lemma
  (requires (r < q))
  (ensures  (r + q * b < q * (b+1)))
let lemma_euclidean_division r b q = ()

private val lemma_factorise: a:nat -> b:nat -> Lemma (a + a * b == a * (b + 1))
let lemma_factorise a b = ()

val lemma_little_endian_is_bounded: b:bytes -> Lemma
  (requires True)
  (ensures  (little_endian b < pow2 (8 * Seq.length b)))
  (decreases (Seq.length b))
let rec lemma_little_endian_is_bounded b =
  if Seq.length b = 0 then ()
  else
    begin
    let s = Seq.slice b 1 (Seq.length b) in
    assert(Seq.length s = Seq.length b - 1);
    lemma_little_endian_is_bounded s;
    assert(UInt8.v (Seq.index b 0) < pow2 8);
    assert(little_endian s < pow2 (8 * Seq.length s));
    assert(little_endian b < pow2 8 + pow2 8 * pow2 (8 * (Seq.length b - 1)));
    lemma_euclidean_division (UInt8.v (Seq.index b 0)) (little_endian s) (pow2 8);
    assert(little_endian b <= pow2 8 * (little_endian s + 1));
    assert(little_endian b <= pow2 8 * pow2 (8 * (Seq.length b - 1)));
    Math.Lemmas.pow2_plus 8 (8 * (Seq.length b - 1));
    lemma_factorise 8 (Seq.length b - 1)
    end

val lemma_big_endian_is_bounded: b:bytes -> Lemma
  (requires True)
  (ensures  (big_endian b < pow2 (8 * Seq.length b)))
  (decreases (Seq.length b))
  [SMTPat (big_endian b)]
let rec lemma_big_endian_is_bounded b =
  if Seq.length b = 0 then ()
  else
    begin
    let s = Seq.slice b 0 (Seq.length b - 1) in
    assert(Seq.length s = Seq.length b - 1);
    lemma_big_endian_is_bounded s;
    assert(UInt8.v (Seq.last b) < pow2 8);
    assert(big_endian s < pow2 (8 * Seq.length s));
    assert(big_endian b < pow2 8 + pow2 8 * pow2 (8 * (Seq.length b - 1)));
    lemma_euclidean_division (UInt8.v (Seq.last b)) (big_endian s) (pow2 8);
    assert(big_endian b <= pow2 8 * (big_endian s + 1));
    assert(big_endian b <= pow2 8 * pow2 (8 * (Seq.length b - 1)));
    Math.Lemmas.pow2_plus 8 (8 * (Seq.length b - 1));
    lemma_factorise 8 (Seq.length b - 1)
    end


#reset-options "--initial_fuel 0 --max_fuel 0"

val lemma_little_endian_lt_2_128: b:bytes {Seq.length b <= 16} -> Lemma
  (requires True)
  (ensures  (little_endian b < pow2 128))
  [SMTPat (little_endian b)]
let lemma_little_endian_lt_2_128 b =
  lemma_little_endian_is_bounded b;
  if Seq.length b = 16 then ()
  else Math.Lemmas.pow2_lt_compat 128 (8 * Seq.length b)


#reset-options "--z3rlimit 100 --max_fuel 1 --initial_fuel 1"

val uint8_to_uint128: a:UInt8.t -> Tot (b:UInt128.t{UInt128.v b == UInt8.v a})
let uint8_to_uint128 a = FStar.UInt128.uint64_to_uint128 (uint8_to_uint64 a)


// turns an integer into a bytestream, little-endian
val little_bytes: 
  len:UInt32.t -> n:nat{n < pow2 (8 * v len)} ->
  Tot (b:lbytes (v len) {n == little_endian b}) (decreases (v len))
let rec little_bytes len n = 
  if len = 0ul then 
    Seq.empty 
  else
    let len = len -^ 1ul in 
    let byte = UInt8.uint_to_t (n % 256) in
    let n' = n / 256 in 
    Math.Lemmas.pow2_plus 8 (8 * v len);
    assert(n' < pow2 (8 * v len ));
    let b' = little_bytes len n' in
    let b = cons byte b' in
    assert(Seq.equal b' (tail b));
    b

#reset-options "--initial_fuel 1 --max_fuel 1 --initial_ifuel 0 --max_ifuel 0"


(* injectivity proofs for byte encodings *) 

type word = b:Seq.seq UInt8.t {Seq.length b <= 16}
open FStar.Math.Lib
open FStar.Math.Lemmas

private let endian_is_injective q r q' r' : Lemma
  (requires UInt8.v r + pow2 8 * q = UInt8.v r' + pow2 8 * q')
  (ensures r = r' /\ q = q') =
  lemma_mod_injective (pow2 8) (UInt8.v r) (UInt8.v r')

private let big_endian_step (b:word{length b > 0}) : 
  Lemma (big_endian b = U8.v (last b) + pow2 8 * big_endian (slice b 0 (length b - 1))) =
  ()

#reset-options "--z3rlimit 100"
val lemma_big_endian_inj: b:word -> b':word {length b = length b'} -> Lemma
  (requires big_endian b = big_endian b')
  (ensures b == b')
val lemma_big_endian_inj: b:word -> b':word {length b = length b'} -> Lemma
  (requires big_endian b = big_endian b')
  (ensures b == b')
  (decreases (length b))

    b: FStar.Old.Endianness.word ->
    b': FStar.Old.Endianness.word{FStar.Seq.Base.length b = FStar.Seq.Base.length b'}
  -> FStar.Pervasives.Lemma
      (requires FStar.Old.Endianness.big_endian b = FStar.Old.Endianness.big_endian b')
      (ensures b == b')
      (decreases FStar.Seq.Base.length b)