master f971a61: Don't rely on bignums in ntlm.el

[Mattias Engdegård]

branch: master
commit f971a612a92eea4c8aab6b002d7998bb0b6f5ca1
Author: Mattias Engdegård <mattiase@acm.org>
Commit: Mattias Engdegård <mattiase@acm.org>

    Don't rely on bignums in ntlm.el
    
    Since ntlm.el is distributed as a separate package in GNU ELPA and
    should be able to run on older Emacs versions without bignums,
    we cannot make use of them here.  See discussion at
    https://lists.gnu.org/archive/html/emacs-devel/2020-10/msg01665.html.
    Instead, we add a small poor man's bignum implementation.
    
    * lisp/net/ntlm.el (ntlm--bignat-of-int, ntlm--bignat-add)
    (ntlm--bignat-shift-left, ntlm--bignat-mul-byte, ntlm--bignat-mul)
    (ntlm--bignat-of-string, ntlm--bignat-of-digits)
    (ntlm--bignat-to-int64): New.
    (ntlm--time-to-timestamp): Use the ntlm--bignat- functions instead
    of Lisp integers.
    * test/lisp/net/ntlm-tests.el: New file.
---
 lisp/net/ntlm.el            | 88 +++++++++++++++++++++++++++++++++++++++------
 test/lisp/net/ntlm-tests.el | 52 +++++++++++++++++++++++++++
 2 files changed, 129 insertions(+), 11 deletions(-)

diff --git a/lisp/net/ntlm.el b/lisp/net/ntlm.el
index 9401430..6d1cf2d 100644
--- a/lisp/net/ntlm.el
+++ b/lisp/net/ntlm.el
@@ -132,23 +132,89 @@ is not given."
            domain                              ;buffer field
            ))))
 
+;; Poor man's bignums: natural numbers represented as lists of bytes
+;; in little-endian order.
+;; When this code no longer needs to run on Emacs 26 or older, all this
+;; silliness should be simplified to use ordinary Lisp integers.
+
+(eval-and-compile                       ; for compile-time simplification
+  (defun ntlm--bignat-of-int (x)
+    "Convert the natural number X into a bignat."
+    (declare (pure t))
+    (and (not (zerop x))
+         (cons (logand x #xff) (ntlm--bignat-of-int (ash x -8)))))
+
+  (defun ntlm--bignat-add (a b &optional carry)
+    "Add the bignats A and B and the natural number CARRY."
+    (declare (pure t))
+    (and (or a b (and carry (not (zerop carry))))
+         (let ((s (+ (if a (car a) 0)
+                     (if b (car b) 0)
+                     (or carry 0))))
+           (cons (logand s #xff)
+                 (ntlm--bignat-add (cdr a) (cdr b) (ash s -8))))))
+
+  (defun ntlm--bignat-shift-left (x n)
+    "Multiply the bignat X by 2^{8N}."
+    (declare (pure t))
+    (if (zerop n) x (ntlm--bignat-shift-left (cons 0 x) (1- n))))
+
+  (defun ntlm--bignat-mul-byte (a b)
+    "Multiply the bignat A with the byte B."
+    (declare (pure t))
+    (let ((p (mapcar (lambda (x) (* x b)) a)))
+      (ntlm--bignat-add
+       (mapcar (lambda (x) (logand x #xff)) p)
+       (cons 0 (mapcar (lambda (x) (ash x -8)) p)))))
+
+  (defun ntlm--bignat-mul (a b)
+    "Multiply the bignats A and B."
+    (declare (pure t))
+    (and a b (ntlm--bignat-add (ntlm--bignat-mul-byte a (car b))
+                               (cons 0 (ntlm--bignat-mul a (cdr b))))))
+
+  (defun ntlm--bignat-of-string (s)
+    "Convert the string S (in decimal) to a bignat."
+    (declare (pure t))
+    (ntlm--bignat-of-digits (reverse (string-to-list s))))
+
+  (defun ntlm--bignat-of-digits (digits)
+    "Convert the little-endian list DIGITS of decimal digits to a bignat."
+    (declare (pure t))
+    (and digits
+         (ntlm--bignat-add
+          nil
+          (ntlm--bignat-mul-byte (ntlm--bignat-of-digits (cdr digits)) 10)
+          (- (car digits) ?0))))
+
+  (defun ntlm--bignat-to-int64 (x)
+    "Convert the bignat X to a 64-bit little-endian number as a string."
+    (declare (pure t))
+    (apply #'unibyte-string (mapcar (lambda (n) (or (nth n x) 0))
+                                    (number-sequence 0 7))))
+  )
+
 (defun ntlm--time-to-timestamp (time)
   "Convert TIME to an NTLMv2 timestamp.
 Return a unibyte string representing the number of tenths of a
 microsecond since January 1, 1601 as a 64-bit little-endian
 signed integer.  TIME must be on the form (HIGH LOW USEC PSEC)."
-  (let* ((s (+ (ash (nth 0 time) 16) (nth 1 time)))
-         (us (nth 2 time))
-         (ps (nth 3 time))
+  (let* ((s-hi (ntlm--bignat-of-int (nth 0 time)))
+         (s-lo (ntlm--bignat-of-int (nth 1 time)))
+         (s (ntlm--bignat-add (ntlm--bignat-shift-left s-hi 2) s-lo))
+         (us*10 (ntlm--bignat-of-int (* (nth 2 time) 10)))
+         (ps/1e5 (ntlm--bignat-of-int (/ (nth 3 time) 100000)))
+        ;; tenths of microseconds between 1601-01-01 and 1970-01-01
+         (to-unix-epoch (ntlm--bignat-of-string "116444736000000000"))
          (tenths-of-us-since-jan-1-1601
-          (+ (* s 10000000) (* us 10) (/ ps 100000)
-            ;; tenths of microseconds between 1601-01-01 and 1970-01-01
-            116444736000000000)))
-    (apply #'unibyte-string
-           (mapcar (lambda (i)
-                     (logand (ash tenths-of-us-since-jan-1-1601 (* i -8))
-                             #xff))
-                   (number-sequence 0 7)))))
+          (ntlm--bignat-add
+           (ntlm--bignat-add
+            (ntlm--bignat-add
+             (ntlm--bignat-mul s (ntlm--bignat-of-int 10000000))
+             us*10)
+            ps/1e5)
+           to-unix-epoch)))
+    (ntlm--bignat-to-int64 tenths-of-us-since-jan-1-1601)))
 
 (defun ntlm-compute-timestamp ()
   "Current time as an NTLMv2 timestamp, as a unibyte string."
diff --git a/test/lisp/net/ntlm-tests.el b/test/lisp/net/ntlm-tests.el
new file mode 100644
index 0000000..e515ebe
--- /dev/null
+++ b/test/lisp/net/ntlm-tests.el
@@ -0,0 +1,52 @@
+;;; ntlm-tests.el --- tests for ntlm.el            -*- lexical-binding: t -*-
+
+;; Copyright (C) 2020 Free Software Foundation, Inc.
+
+;; This file is part of GNU Emacs.
+
+;; GNU Emacs is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+
+;; GNU Emacs is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+;; GNU General Public License for more details.
+
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.
+
+(require 'ert)
+(require 'ntlm)
+
+;; This is the Lisp bignum implementation of `ntlm--time-to-timestamp',
+;; for reference.
+(defun ntlm-tests--time-to-timestamp (time)
+  "Convert TIME to an NTLMv2 timestamp.
+Return a unibyte string representing the number of tenths of a
+microsecond since January 1, 1601 as a 64-bit little-endian
+signed integer.  TIME must be on the form (HIGH LOW USEC PSEC)."
+  (let* ((s (+ (ash (nth 0 time) 16) (nth 1 time)))
+         (us (nth 2 time))
+         (ps (nth 3 time))
+         (tenths-of-us-since-jan-1-1601
+          (+ (* s 10000000) (* us 10) (/ ps 100000)
+            ;; tenths of microseconds between 1601-01-01 and 1970-01-01
+            116444736000000000)))
+    (apply #'unibyte-string
+           (mapcar (lambda (i)
+                     (logand (ash tenths-of-us-since-jan-1-1601 (* i -8))
+                             #xff))
+                   (number-sequence 0 7)))))
+
+(ert-deftest ntlm-time-to-timestamp ()
+  ;; Verify poor man's bignums in implementation that can run on Emacs < 27.1.
+  (let ((time '(24471 63910 412962 0)))
+    (should (equal (ntlm--time-to-timestamp time)
+                   (ntlm-tests--time-to-timestamp time))))
+  (let ((time '(397431 65535 999999 999999)))
+    (should (equal (ntlm--time-to-timestamp time)
+                   (ntlm-tests--time-to-timestamp time)))))
+
+(provide 'ntlm-tests)