• Top
  • Documentation
  • Books
  • Boolean-reasoning
  • Projects
  • Debugging
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
    • Kestrel-books
    • X86isa
      • Program-execution
      • Sdm-instruction-set-summary
      • Tlb
      • Booting-linux
      • Introduction
      • Asmtest
      • X86isa-build-instructions
      • Publications
      • Contributors
      • Machine
        • X86isa-state
        • Syscalls
        • Cpuid
        • Linear-memory
          • Reasoning-about-memory-reads-and-writes
          • Rml256
          • Wml256
          • Rml128
          • Rml80
          • Program-location
          • Rml64
          • Wml128
          • Rml48
          • Rml32
          • Rml08
          • Rml16
          • Wml80
          • Byte-listp
          • Wml64
          • Wml08
          • Wml48
          • Parametric-memory-reads-and-writes
          • Combine-n-bytes
          • Wml32
          • Program-at
          • Wml16
          • Combine-bytes
          • Write-canonical-address-to-memory-user-exec
          • Write-canonical-address-to-memory
          • Wml-size
          • Rml-size
          • Riml64
          • Riml32
          • Riml16
          • Riml08
          • Wiml64
          • Wiml32
          • Wiml16
          • Wiml08
          • Wiml-size
          • Generate-xr-over-write-thms
          • Generate-write-fn-over-xw-thms
          • Generate-read-fn-over-xw-thms
          • Riml-size
        • Rflag-specifications
        • Characterizing-undefined-behavior
        • Top-level-memory
        • App-view
        • X86-decoder
        • Physical-memory
        • Decoding-and-spec-utils
        • Instructions
        • Register-readers-and-writers
        • X86-modes
        • Segmentation
        • Other-non-deterministic-computations
        • Environment
        • Paging
      • Implemented-opcodes
      • To-do
      • Proof-utilities
      • Peripherals
      • Model-validation
      • Modelcalls
      • Concrete-simulation-examples
      • Utils
      • Debugging-code-proofs
    • Axe
    • Execloader
  • Math
  • Testing-utilities

• Linear-memory

Program-location

Definitions and Theorems

Function: byte-listp

(defun byte-listp (x)
  (declare (xargs :guard t))
  (let ((__function__ 'byte-listp))
    (declare (ignorable __function__))
    (if (equal x nil)
        t
      (and (consp x)
           (n08p (car x))
           (byte-listp (cdr x))))))

Theorem: byte-listp-implies-true-listp

(defthm byte-listp-implies-true-listp
  (implies (byte-listp x) (true-listp x))
  :rule-classes :forward-chaining)

Theorem: n08p-element-of-byte-listp

(defthm n08p-element-of-byte-listp
 (implies (and (byte-listp acc)
               (natp m)
               (< m (len acc)))
          (unsigned-byte-p 8 (nth m acc)))
 :rule-classes
 (:rewrite
  (:type-prescription
      :corollary (implies (and (byte-listp acc)
                               (natp m)
                               (< m (len acc)))
                          (natp (nth m acc)))
      :hints
      (("Goal" :in-theory '(unsigned-byte-p integer-range-p natp))))
  (:linear
   :corollary (implies (and (byte-listp acc)
                            (natp m)
                            (< m (len acc)))
                       (and (<= 0 (nth m acc))
                            (< (nth m acc) 256)))
   :hints
   (("Goal"
        :in-theory '(unsigned-byte-p integer-range-p (:e expt)))))))

Theorem: repeat-byte-listp

(defthm repeat-byte-listp
  (implies (unsigned-byte-p 8 m)
           (byte-listp (acl2::repeat n m)))
  :rule-classes (:type-prescription :rewrite))

Theorem: len-of-nthcdr-byte-listp

(defthm len-of-nthcdr-byte-listp
  (implies (and (< m (len acc)) (natp m))
           (equal (len (nthcdr m acc))
                  (- (len acc) m))))

Theorem: byte-listp-revappend

(defthm byte-listp-revappend
  (implies (forced-and (byte-listp lst1)
                       (byte-listp lst2))
           (byte-listp (revappend lst1 lst2)))
  :rule-classes :type-prescription)

Theorem: true-listp-make-list-ac

(defthm true-listp-make-list-ac
  (implies (true-listp ac)
           (true-listp (make-list-ac n val ac)))
  :rule-classes :type-prescription)

Theorem: reverse-byte-listp

(defthm reverse-byte-listp
  (implies (byte-listp x)
           (byte-listp (reverse x)))
  :rule-classes (:type-prescription :rewrite))

Theorem: byte-listp-append

(defthm byte-listp-append
  (implies (forced-and (byte-listp lst1)
                       (byte-listp lst2))
           (byte-listp (append lst1 lst2)))
  :rule-classes (:rewrite :type-prescription))

Theorem: make-list-ac-byte-listp

(defthm make-list-ac-byte-listp
  (implies (and (byte-listp x) (n08p m))
           (byte-listp (make-list-ac n m x)))
  :rule-classes (:type-prescription :rewrite))

Function: combine-bytes

(defun combine-bytes (bytes)
  (declare (xargs :guard (byte-listp bytes)))
  (let ((__function__ 'combine-bytes))
    (declare (ignorable __function__))
    (if (endp bytes)
        0
      (logapp 8
              (if (mbt (unsigned-byte-p 8 (car bytes)))
                  (car bytes)
                0)
              (combine-bytes (cdr bytes))))))

Theorem: natp-combine-bytes

(defthm natp-combine-bytes
  (implies (force (byte-listp bytes))
           (natp (combine-bytes bytes)))
  :rule-classes :type-prescription)

Theorem: unsigned-byte-p-of-combine-bytes

(defthm unsigned-byte-p-of-combine-bytes
  (implies (and (equal n (ash (len bytes) 3))
                (byte-listp bytes))
           (unsigned-byte-p n (combine-bytes bytes)))
  :rule-classes
  ((:rewrite)
   (:linear :corollary (implies (and (equal n (ash (len bytes) 3))
                                     (byte-listp bytes))
                                (<= 0 (combine-bytes bytes))))))

Theorem: size-of-combine-bytes

(defthm size-of-combine-bytes
  (implies (and (equal l (len bytes))
                (byte-listp bytes))
           (< (combine-bytes bytes)
              (expt 2 (ash l 3))))
  :rule-classes :linear)

Theorem: byte-listp-of-nthcdr

(defthm byte-listp-of-nthcdr
  (implies (byte-listp xs)
           (byte-listp (nthcdr n xs))))

Theorem: byte-listp-of-take

(defthm byte-listp-of-take
  (implies (and (byte-listp xs) (<= n (len xs)))
           (byte-listp (take n xs))))

Function: combine-n-bytes

(defun combine-n-bytes (low num bytes)
  (declare (xargs :guard (and (natp low)
                              (natp num)
                              (byte-listp bytes))))
  (declare (xargs :guard (<= (+ low num) (len bytes))))
  (let ((__function__ 'combine-n-bytes))
    (declare (ignorable __function__))
    (if (mbt (and (<= (+ low num) (len bytes))
                  (byte-listp bytes)
                  (natp low)
                  (natp num)))
        (combine-bytes (take num (nthcdr low bytes)))
      0)))

Theorem: combine-bytes-and-take-degenerate-case-1

(defthm combine-bytes-and-take-degenerate-case-1
  (implies (zp n)
           (equal (combine-bytes (take n bytes))
                  0)))

Theorem: combine-bytes-and-take-degenerate-case-2

(defthm combine-bytes-and-take-degenerate-case-2
  (equal (combine-bytes (take n nil)) 0))

Theorem: natp-of-combine-bytes-of-take

(defthm natp-of-combine-bytes-of-take
  (implies (byte-listp bytes)
           (<= 0 (combine-bytes (take num bytes)))))

Theorem: natp-combine-n-bytes

(defthm natp-combine-n-bytes
 (implies (force (byte-listp bytes))
          (natp (combine-n-bytes low num bytes)))
 :rule-classes
 ((:type-prescription)
  (:linear
      :corollary (implies (byte-listp bytes)
                          (<= 0 (combine-n-bytes low num bytes))))))

Theorem: unsigned-byte-p-of-combine-n-bytes

(defthm unsigned-byte-p-of-combine-n-bytes
  (implies (and (equal n (ash num 3)) (natp num))
           (unsigned-byte-p n (combine-n-bytes low num bytes))))

Theorem: size-of-combine-n-bytes

(defthm size-of-combine-n-bytes
  (< (combine-n-bytes low num bytes)
     (expt 2 (ash num 3)))
  :rule-classes :linear)

Function: program-at

(defun program-at (prog-addr bytes x86)
 (declare (xargs :stobjs (x86)))
 (declare
  (xargs
      :guard (and (canonical-address-p prog-addr)
                  (canonical-address-p (+ -1 (len bytes) prog-addr))
                  (byte-listp bytes))
      :non-executable t))
 (prog2$ (acl2::throw-nonexec-error 'program-at
                                    (list prog-addr bytes x86))
         (let ((__function__ 'program-at))
           (declare (ignorable __function__))
           (b* (((mv flg bytes-read ?x86)
                 (rb (len bytes) prog-addr :x x86)))
             (and (equal flg nil)
                  (equal bytes-read
                         (combine-n-bytes 0 (len bytes)
                                          bytes)))))))

Theorem: program-at-xw-in-app-view

(defthm program-at-xw-in-app-view
  (implies (and (app-view x86)
                (not (equal fld :mem))
                (not (equal fld :app-view)))
           (equal (program-at addr bytes (xw fld index value x86))
                  (program-at addr bytes x86))))