3 ;;; This file isn't a program as such: rather, it's a collection of handy
4 ;;; functions which can be used in an interactive session.
6 ;;;--------------------------------------------------------------------------
7 ;;; General permutation utilities.
10 "Randomly permute the elements of the vector V. Return V."
16 (rotatef (aref v i) (aref v (1- k))))))))
18 (defun identity-permutation (n)
19 "Return the do-nothing permutation on N elements."
20 (let ((v (make-array n :element-type 'fixnum)))
21 (dotimes (i n v) (setf (aref v i) i))))
23 (defun invert-permutation (p)
24 "Given a permutation P, return its inverse."
25 (let* ((n (length p)) (p-inv (make-array n :element-type 'fixnum)))
26 (dotimes (i n) (setf (aref p-inv (aref p i)) i))
29 (defun next-permutation (v)
30 "Adjust V so that it reflects the next permutation in ascending order.
32 V should be a vector of real numbers. Returns V if successful, or nil if
33 there are no more permutations."
35 ;; The tail of the vector consists of a sequence ... A, Z, Y, X, ..., where
36 ;; Z > Y > X ... is in reverse order, and A < Z. The next permutation is
37 ;; then the smallest out of Z, Y, X, ... which is larger than A, followed
38 ;; by the remaining elements in ascending order.
40 ;; Equivalently, reverse the tail Z, Y, X, ... so we have A, ... X, Y, Z,
41 ;; and swap A with the next larger element.
47 (loop (when (zerop k) (return-from next-permutation nil))
53 (do ((i (1+ k) (1+ i))
56 (rotatef (aref v i) (aref v j)))
57 (do ((i (- n 2) (1- i)))
58 ((or (<= i k) (< (aref v i) x))
59 (rotatef (aref v k) (aref v (1+ i)))))
62 (defun make-index-mask (w mask-expr)
63 "Construct a bitmask based on bitwise properties of the bit indices.
65 The function returns a W-bit mask in which each bit is set if MASK-EXPR
66 of true of the bit's index. MASK-EXPR may be one of the following:
68 * I -- an integer I is true if bit I of the bit index is set;
69 * (not EXPR) -- is true if EXPR is false;
70 * (and EXPR EXPR ...) -- is true if all of the EXPRs are true; and
71 * (or EXPR EXPR ...) -- is true if any of the EXPRs is true."
73 (let ((max-bit (1- (integer-length (1- w))))
76 (labels ((interpret (expr)
77 (cond ((and (integerp expr) (<= 0 expr max-bit))
79 ((and (consp expr) (eq (car expr) 'not)
81 (not (interpret (cadr expr))))
82 ((and (consp expr) (eq (car expr) 'and))
83 (every #'interpret (cdr expr)))
84 ((and (consp expr) (eq (car expr) 'or))
85 (some #'interpret (cdr expr)))
87 (error "unknown mask expression ~S" expr)))))
88 (when (interpret mask-expr)
89 (setf (ldb (byte 1 i) mask) 1))))))
91 (defun make-permutation-network (w steps)
92 "Construct a permutation network.
94 The integer W gives the number of bits to be acted upon. The STEPS are a
95 list of instructions of the following forms:
97 * (SHIFT . MASK) -- a pair of integers is treated literally;
99 * (SHIFT MASK-EXPR) -- the SHIFT is literal, but the MASK-EXPR is
100 processed by `make-index-mask' to calculate the mask;
102 * (:invert I) -- make an instruction which inverts the sense of the
105 * (:exchange I J) -- make an instruction which exchanges index bits I
108 * (:exchange-invert I J) -- make an instruction which exchanges and
109 inverts index bits I and J.
111 The output is a list of primitive (SHIFT . MASK) steps, indicating that
112 the bits of the input selected by MASK are to be swapped with the bits
113 selected by (ash MASK SHIFT)."
115 (let ((max-mask (1- (ash 1 w)))
117 (max-bit (1- (integer-length (1- w))))
120 (cond ((and (consp step)
121 (integerp (car step)) (<= 0 (car step) max-shift)
122 (integerp (cdr step)) (<= 0 (cdr step) max-mask))
125 (integerp (car step)) (<= 0 (car step) max-shift)
127 (push (cons (car step) (make-index-mask w (cadr step))) list))
129 (eq (car step) :invert)
130 (integerp (cadr step)) (<= 0 (cadr step) max-bit)
132 (let ((i (cadr step)))
133 (push (cons (ash 1 i) (make-index-mask w `(not ,i))) list)))
135 (eq (car step) :exchange)
136 (integerp (cadr step)) (integerp (caddr step))
137 (<= 0 (cadr step) (caddr step) max-bit)
139 (let ((i (cadr step)) (j (caddr step)))
140 (push (cons (- (ash 1 j) (ash 1 i))
141 (make-index-mask w `(and ,i (not ,j))))
144 (eq (car step) :exchange-invert)
145 (integerp (cadr step)) (integerp (caddr step))
146 (<= 0 (cadr step) (caddr step) max-bit)
148 (let ((i (cadr step)) (j (caddr step)))
149 (push (cons (+ (ash 1 i) (ash 1 j))
150 (make-index-mask w `(and (not ,i) (not ,j))))
153 (error "unknown permutation step ~S" step))))
156 ;;;--------------------------------------------------------------------------
157 ;;; Permutation network diagnostics.
159 (defun print-permutation-network (steps &optional (stream *standard-output*))
160 "Print a description of the permutation network STEPS to STREAM.
162 A permutation network consists of a list of pairs
166 indicating that the bits selected by MASK, and those SHIFT bits to the
167 left, should be exchanged.
169 The output is intended to be human-readable and is subject to change."
171 (let ((shiftwd 1) (maskwd 2))
173 ;; Determine suitable print widths for shifts and masks.
175 (let ((shift (car step)) (mask (cdr step)))
176 (let ((swd (1+ (floor (log shift 10))))
177 (mwd (ash 1 (- (integer-length (1- (integer-length mask)))
179 (when (> swd shiftwd) (setf shiftwd swd))
180 (when (> mwd maskwd) (setf maskwd mwd)))))
182 ;; Print the display.
183 (pprint-logical-block (stream steps :prefix "(" :suffix ")")
186 (let ((shift (car step)) (mask (cdr step)))
188 ;; Separate entries with newlines.
189 (cond (first (setf first nil))
190 (t (pprint-newline :mandatory stream)))
194 ;; Determine the list of exchanges implied by the mask.
195 (dotimes (i (integer-length mask))
196 (when (logbitp i mask)
197 (push (cons i (+ i shift)) swaps)))
198 (setf swaps (nreverse swaps))
201 (format stream "~@<(~;~vD #x~(~v,'0X~) ~8I~:@_~W~;)~:>"
202 shiftwd shift maskwd mask swaps))))))
204 ;; Print a final newline following the close parenthesis.
207 (defun demonstrate-permutation-network
211 (stream *standard-output*))
212 "Print, on STREAM, a demonstration of the permutation STEPS.
214 The output is intended to be useful to human readers and is subject to
215 change. Currently, it prints a sequence of diagrams on STREAM. The left
216 hand side of each row shows a map of which bits are affected: `-' means
217 that the bit remains in the same position, `*' means that it moves
218 forward, and `#' means that it moves back; each `*' pairs with the
219 earliest unpaired `#' marker. The right hand side shows the arrangement
220 of the original input bits.
222 If OFFSETS is non-nil, then also print a table of offsets showing how far
223 each bit has yet to move.
225 If REFERENCE is not nil, then print a final pair of diagrams. This time,
226 the map shows `-' for correct bits and `x' for incorrect ones, with the
227 right hand side showing the expected arrangement of input bits.
229 The function returns non-nil if the STEPS resulted in the REFERENCE
230 permutation, and nil if either the STEPS are incorrect or no REFERENCE was
233 (flet ((apply-step (shift mask v)
235 (when (logbitp k mask)
236 (rotatef (aref v k) (aref v (+ k shift)))))))
238 (let* ((v (identity-permutation n))
240 (let ((e (identity-permutation n)))
241 (dolist (step steps e)
242 (let ((shift (car step)) (mask (cdr step)))
243 (apply-step shift mask e))))))
244 (end-inv (invert-permutation end))
245 (mapwd (ceiling (sqrt n)))
246 (ixwd (length (format nil "~D" (1- n)))))
248 (flet ((show-stage (shift mask v)
249 (do ((i 0 (+ i mapwd)))
251 (write-string ";; " stream)
254 (when (plusp j) (write-char #\space stream))
255 (write-char (cond ((>= k n)
260 (logbitp (- k shift) mask))
265 (write-string " | " stream)
270 (when (plusp j) (write-char #\space stream))
272 (format stream "~v@T" (1+ ixwd)))
274 (format stream "~*~[~2:*~vD~:;~2:*~v@D~]"
276 (- (aref end-inv (aref v k)) k))))))
277 (write-string " | " stream))
279 (dotimes (j (min mapwd (- n i)))
281 (when (plusp j) (write-char #\space stream))
282 (format stream "~vD" ixwd (aref v k))))
289 (let ((shift (car step)) (mask (cdr step)))
290 (apply-step shift mask v)
291 (format stream ";;~%")
292 (show-stage shift mask v)))
294 (let ((ok (not (null reference))))
296 (format stream ";;~%")
297 (do ((i 0 (+ i mapwd)))
299 (write-string ";; " stream)
302 (when (plusp j) (write-char #\space stream))
303 (write-char (cond ((>= k n) #\space)
304 ((/= (aref v k) (aref reference k)) #\x)
307 (write-string " | " stream)
308 (dotimes (j (min mapwd (- n i)))
310 (when (plusp j) (write-char #\space stream))
311 (format stream "~vD" ixwd (aref reference k))))
313 (unless (every #'= v reference)
315 (format stream "~:[FAIL~;pass~]~%" ok))
318 ;;;--------------------------------------------------------------------------
321 (defun compute-benes-step (n p p-inv bit clear-input)
322 "Compute a single layer of a Beneš network.
324 N is a fixnum. P is a vector of fixnums defining a permutation: for each
325 output bit position i (numbering the least significant bit 0), element i
326 gives the number of the input which should end up in that position; P-INV
327 gives the inverse permutation in the same form. BIT is a power of 2 which
328 gives the distance between bits we should consider. CLEAR-INPUT is
329 a (generalized) boolean: if true, we attempt to do no work on the input
330 side; if false, we try to do no work on the output side. The length of P
331 must be at least (logior N BIT).
333 The output consists of a pair of masks M0 and M1, to be used on the input
334 and output sides respectively. The permutation stage, applied to an input
337 (let ((tmp (logand (logxor x (ash x (- bit))) mask)))
338 (logxor x tmp (ash tmp bit)))
340 The critical property of the masks is that it's possible to compute an
341 inner permutation, mapping the output of the M0 stage to the input of the
342 M1 stage, such that (a) the overall composition of the three permutations
343 is the given permutation P, and (b) the distances that the bits need to
344 be moved by the inner permutation all have BIT clear.
346 The resulting permutation will attempt to avoid touching elements at
347 indices greater than N. This attempt will succeed if all such elements
348 contain values equal to their indices.
350 By appropriately composing layers computed by this function, then, it's
351 possible to perform an arbitrary permutation of 2^n bits in 2 n - 1 simple
352 steps like the one above."
354 ;; Consider the following problem. You're given two equally-sized
355 ;; collections of things, called `left' and `right'. Each left thing is
356 ;; attached to exactly one right thing with a string, and /vice versa/.
357 ;; Furthermore, the left things, and the right things, are each linked
358 ;; together in pairs, so each pair has two strings coming out of it. Our
359 ;; job is to paint the strings so that each linked pair of things has one
360 ;; red string and one blue string.
362 ;; This is quite straightforward. Pick a pair whose strings aren't yet
363 ;; coloured, and colour one of its strings, chosen arbitrarily, red. Find
364 ;; the pair at the other end of this red string. If the two other things
365 ;; in these two pairs are connected, then paint that string blue and move
366 ;; on. Otherwise, both things have an uncoloured string, so paint both of
367 ;; them blue and trace along these now blue strings to find two more thing
368 ;; pairs. Again, the other thing in each pair has an uncoloured string.
369 ;; If these things share the /same/ string, paint it red and move on.
370 ;; Otherwise, paint both strings red, trace, and repeat. Eventually, we'll
371 ;; find two things joined by the same string, each paired with another
372 ;; thing whose strings we've just painted the same colour. Once we're
373 ;; done, we'll have painted a cycle's worth of strings, and each pair of
374 ;; things will have either both of its strings painted different colours,
375 ;; or neither of them.
377 ;; The right things are the integers 0, 1, ..., n - 1, where n is some
378 ;; power of 2, paired according to whether they differ only in BIT. The
379 ;; left things are the same integers, connected to the right things
380 ;; according to the permutation P: the right thing labelled i is connected
381 ;; to the left thing labelled P(i). Similarly, two left things are paired
382 ;; if their labels P(i) and P(j) differ only in BIT. We're going to paint
383 ;; a string red if we're going to arrange to clear BIT in the labels at
384 ;; both ends, possibly by swapping the two labels, and paint it red if
385 ;; we're going to arrange to set BIT. Once we've done this, later stages
386 ;; of the filter will permute the red- and blue-painted things
389 (let ((m0 0) (m1 0) (done 0))
391 ;; Now work through the permutation cycles.
392 (do ((i (1- n) (1- i)))
395 ;; Skip if we've done this one already.
396 (unless (or (plusp (logand i bit))
399 ;; Find the other associated values.
400 (let* ((i0 i) (i1 (aref p-inv i))
401 (sense (cond ((>= (logior i0 bit) n) 0)
402 (clear-input (logand i0 bit))
403 (t (logand i1 bit)))))
406 (format t ";; new cycle: i0 = ~D, j0 = ~D; i1 = ~D, j1 = ~D~%"
410 ;; Mark this index as done.
411 (setf (ldb (byte 1 i0) done) 1)
412 #+noise (format t ";; done = #x~2,'0X~%" done)
414 ;; Now trace round the cycle.
417 ;; Mark this index as done.
418 (setf (ldb (byte 1 (logandc2 i0 bit)) done) 1)
419 #+noise (format t ";; done = #x~2,'0X~%" done)
421 ;; Swap the input and output pairs if necessary.
422 (unless (= (logand i0 bit) sense)
424 (format t ";; swap input: ~D <-> ~D~%"
425 (logandc2 i0 bit) (logior i0 bit))
426 (setf (ldb (byte 1 (logandc2 i0 bit)) m0) 1))
427 (unless (= (logand i1 bit) sense)
429 (format t ";; swap output: ~D <-> ~D~%"
430 (logandc2 i1 bit) (logior i1 bit))
431 (setf (ldb (byte 1 (logandc2 i1 bit)) m1) 1))
433 ;; Advance around the cycle.
434 (let* ((j0 (logxor i0 bit))
436 (next-i1 (aref p-inv j0))
437 (next-i0 (aref p j1)))
438 (when (= next-i0 j0) (return))
441 sense (logxor sense bit)))
444 (format t ";; advance: i0 = ~D, j0 = ~D; i1 = ~D, j1 = ~D~%"
446 i1 (logxor i1 bit))))))
450 (defun compute-final-benes-step (n p p-inv bit)
451 "Determine the innermost stage of a Beneš network.
453 N is a fixnum. P is a vector of fixnums defining a permutation: for each
454 output bit position i (numbering the least significant bit 0), element i
455 gives the number of the input which should end up in that position; P-INV
456 gives the inverse permutation in the same form. BIT is a power of 2 which
457 gives the distance between bits we should consider. The length of P must
458 be at least (logior N BIT).
460 Furthermore, the ith element of P must be equal either to i or to
461 (logxor i BIT); and therefore P-INV must be equal to P.
463 Return the mask such that
465 (let ((tmp (logand (logxor x (ash x (- bit))) mask)))
466 (logxor x tmp (ash tmp bit)))
468 applies the permutation P to the bits of x."
470 (declare (ignorable p-inv))
474 (unless (plusp (logand i bit))
475 (let ((x (aref p i)))
477 (assert (= (logandc2 x bit) i))
479 (assert (= x (aref p-inv i)))
482 (setf (ldb (byte 1 i) m) 1)))))
485 (defun apply-benes-step (p p-inv bit m0 m1)
486 "Apply input and output steps for a Beneš network to a permutation.
488 Given the permutation P and its inverse, and the distance BIT, as passed
489 to `compute-benes-step', and the masks M0 and M1 returned, determine and
490 return the necessary `inner' permutation to be applied between these
491 steps, and its inverse.
493 A permutation-network step, and, in particular, a Beneš step, is an
494 involution, so the change to the vectors P and P-INV can be undone by
495 calling the function again with the same arguments."
497 (flet ((swaps (p p-inv mask)
498 (dotimes (i0 (length p))
499 (when (logbitp i0 mask)
500 (let* ((j0 (logior i0 bit))
502 (j1 (aref p-inv j0)))
505 (rotatef (aref p-inv i0) (aref p-inv j0)))))))
510 (let* ((n (length p)))
512 (assert (= (aref p (aref p-inv i)) i))
513 (assert (= (aref p-inv (aref p i)) i))))))
515 (defun benes-search (p)
516 "Given a bit permutation P, describe a Beneš network implementing P.
518 P is a sequence of fixnums defining a permutation: for each output bit
519 position i (numbering the least significant bit 0), element i gives the
520 number of the input which should end up in that position.
522 The return value is a list of steps of the form
524 (BIT MASK (X . Y) (X' . Y') ...)
526 To implement this permutation step:
528 * given an input X, compute
530 (let ((tmp (logand (logxor x (ash x (- bit))) mask)))
531 (logxor x tmp (ash tmp bit)))
535 * exchange the bits in the positions given in each of the pairs X, Y,
536 ..., where each Y = X + BIT."
538 (let* ((n (length p))
539 (w (ash 1 (integer-length (1- n))))
540 (p (let ((new (make-array w :element-type 'fixnum)))
544 (setf (aref new i) i))
546 (p-inv (invert-permutation p)))
548 (labels ((recurse (todo)
549 ;; Main recursive search. DONE is a mask of the bits which
550 ;; have been searched. Return the number of skipped stages
551 ;; and a list of steps (BIT M0 M1), indicating that (BIT M0)
552 ;; should be performed before the following stages, and
553 ;; (BIT M1) should be performed afterwards.
555 ;; The permutation `p' and its inverse `p-inv' will be
556 ;; modified and restored.
558 (cond ((zerop (logand todo (1- todo)))
559 ;; Only one more bit left. Use the more efficient
560 ;; final-step computation.
562 (let ((m (compute-final-benes-step n p p-inv todo)))
563 (values (if m 0 1) (list (list todo m 0)))))
566 ;; More searching to go. We'll keep the result which
567 ;; maximizes the number of skipped stages.
568 (let ((best-list nil)
571 (flet ((try (bit clear-input)
572 ;; Try a permutation with the given BIT and
573 ;; CLEAR-INPUT arguments to
574 ;; `compute-benes-step'.
576 ;; Compute the next step.
577 (multiple-value-bind (m0 m1)
578 (compute-benes-step n p p-inv
581 ;; Apply the step and recursively
582 ;; determine the inner permutation.
583 (apply-benes-step p p-inv bit m0 m1)
584 (multiple-value-bind (nskip tail)
585 (recurse (logandc2 todo bit))
586 (apply-benes-step p p-inv bit m0 m1)
588 ;; Work out how good this network is.
589 ;; Keep it if it improves over the
591 (when (zerop m0) (incf nskip))
592 (when (zerop m1) (incf nskip))
593 (when (> nskip best-skips)
595 (cons (list bit m0 m1)
600 ;; Work through each bit that we haven't done
601 ;; already, and try skipping both the start and end
603 (do ((bit 1 (ash bit 1)))
605 (when (plusp (logand bit todo))
608 (values best-skips best-list))))))
610 ;; Find the best permutation network.
611 (multiple-value-bind (nskip list) (recurse (1- w))
612 (declare (ignore nskip))
614 ;; Turn the list returned by `recurse' into a list of (SHIFT MASK)
615 ;; entries as expected by everything else.
616 (let ((head nil) (tail nil))
617 (dolist (step list (nconc (nreverse head) tail))
618 (destructuring-bind (bit m0 m1) step
619 (when (plusp m0) (push (cons bit m0) head))
620 (when (plusp m1) (push (cons bit m1) tail)))))))))
622 ;;;--------------------------------------------------------------------------
623 ;;; Special functions for DES permutations.
625 (defun benes-search-des (p &optional attempts)
626 "Search for a Beneš network for a DES 64-bit permutation.
628 P must be a sequence of 64 fixnums, each of which is between 0 and 64
629 inclusive. In the DES convention, bits are numbered with the most-
630 significant bit being bit 1, and increasing towards the least-significant
631 bit, which is bit 64. Each nonzero number must appear at most once, and
632 specifies which input bit must appear in that output position. There may
633 also be any number of zero entries, which mean `don't care'.
635 This function searches for and returns a Beneš network which implements a
636 satisfactory permutation. If ATTEMPTS is nil or omitted, then search
637 exhaustively, returning the shortest network. Otherwise, return the
638 shortest network found after considering ATTEMPTS randomly chosen
639 matching permutations."
641 (let* ((n (length p))
642 (p (map '(vector fixnum)
647 (seen (make-hash-table))
648 (nmissing 0) (missing nil) (indices nil))
650 ;; Find all of the `don't care' slots, and keep track of the bits which
651 ;; have homes to go to.
653 (let ((x (aref p i)))
657 (t (setf (gethash x seen) t)))))
659 ;; Fill in numbers of the input bits which don't have fixed places to go.
660 (setf missing (make-array nmissing :element-type 'fixnum))
663 (unless (gethash i seen)
664 (setf (aref missing j) i)
666 (assert (= j nmissing)))
668 ;; Run the search, printing successes as we find them to keep the user
670 (let ((best nil) (best-length nil))
672 (cond ((eql attempts 0) (return best))
673 (attempts (shuffle missing) (decf attempts))
674 ((null (next-permutation missing)) (return best)))
675 (do ((idx indices (cdr idx))
678 (setf (aref p (car idx)) (aref missing i)))
679 (let* ((benes (benes-search p)) (len (length benes)))
680 (when (or (null best-length)
682 (setf best-length len
684 (print-permutation-network benes)
687 ;;;--------------------------------------------------------------------------
688 ;;; Examples and useful runes.
691 (let* ((ip #(58 50 42 34 26 18 10 2
692 60 52 44 36 28 20 12 4
693 62 54 46 38 30 22 14 6
694 64 56 48 40 32 24 16 8
695 57 49 41 33 25 17 9 1
696 59 51 43 35 27 19 11 3
697 61 53 45 37 29 21 13 5
698 63 55 47 39 31 23 15 7))
699 (fixed-ip (map '(vector fixnum)
700 (lambda (x) (- 64 x))
703 ;; The traditional network.
705 (make-permutation-network
707 '((:exchange-invert 2 5) ; ~2 4 3 ~5 1 0
708 (:exchange-invert 1 4) ; ~2 ~1 3 ~5 ~4 0
709 (:exchange-invert 0 3) ; ~2 ~1 ~0 ~5 ~4 ~3
710 (:exchange-invert 3 4) ; ~2 0 1 ~5 ~4 ~3
711 (:exchange-invert 4 5)))) ; ~0 2 1 ~5 ~4 ~3
713 ;; The new twizzle-optimized network.
715 (make-permutation-network
717 '((:exchange-invert 2 5) ; ~2 4 3 ~5 1 0
718 (:exchange-invert 4 5) ; ~4 2 3 ~5 1 0
719 (:exchange 1 5) ; 1 2 3 ~5 ~4 0
720 (:exchange 3 5) ; 3 2 1 ~5 ~4 0
721 (:exchange-invert 0 5))))) ; ~0 2 1 ~5 ~4 ~3
725 (let ((benes-network (benes-search fixed-ip)))
726 (print-permutation-network benes-network)
727 (demonstrate-permutation-network 64 benes-network :reference fixed-ip))
729 (print-permutation-network trad-network)
730 (demonstrate-permutation-network 64 trad-network :reference fixed-ip)
732 (print-permutation-network new-network)
733 (demonstrate-permutation-network 64 new-network :reference fixed-ip))
736 (benes-search-des #( 0 0 0 0
737 57 49 41 33 25 17 9 1
738 58 50 42 34 26 18 10 2
739 59 51 43 35 27 19 11 3
742 63 55 47 39 31 23 15 7
743 62 54 46 38 30 22 14 6
744 61 53 45 37 29 21 13 5
748 (let ((pc2 (make-array '(8 6)
749 :element-type 'fixnum
750 :initial-contents '((14 17 11 24 1 5)
757 (46 42 50 36 29 32)))))
760 :element-type 'fixnum
762 (loop for i in '(2 4 6 8 1 3 5 7)
764 nconc (loop for j below 6
765 for x = (aref pc2 (1- i) j)
766 collect (if (<= x 32) (+ x 4) (+ x 8)))))