///////////////////////////////////////////////////////////////////////////////
// ring_red_mod3.S: Reduction of a 16-bit unsigned integer modulo 3. //
// This file is part of AVRNTRU, a fast NTRU implementation for 8-bit AVR. //
// Version 1.0.0 (2018-12-17), see for updates. //
// Authors: Johann Groszschaedl and Hao Cheng (University of Luxembourg). //
// License: GPLv3 (see LICENSE file), other licenses available upon request. //
// Copyright (C) 2018-2019 University of Luxembourg //
// ------------------------------------------------------------------------- //
// This program 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. This program 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 this program. If not, //
// see . //
///////////////////////////////////////////////////////////////////////////////
// Function prototype:
// -------------------
//
// Description:
// ------------
//
// Operands:
// ---------
//
// Version history:
// ----------------
// define register names
#define HIBYTE R25 // upper byte of 16-bit UINT to be reduced mod 3
#define LOBYTE R24 // upper byte of 16-bit UINT to be reduced mod 3
#define ZERO R23 // ZERO is always 0
.global ring_red_mod3
.func ring_red_mod3
ring_red_mod3:
// initialize variables
CLR ZERO
// first step: reduction modulo 85*3 = 255 = 2^8 - 1
ADD LOBYTE, HIBYTE //
ADC LOBYTE, ZERO //
// second step: reduction modulo 5*3 = 15 = 2^4 - 1
MOV HIBYTE, LOBYTE //
SWAP HIBYTE // swap the 4-bit nibbles of HIBYTE
ANDI LOBYTE, 0xF //
ANDI HIBYTE, 0xF //
ADD LOBYTE, HIBYTE //
MOV HIBYTE, LOBYTE //
SWAP HIBYTE // swap the 4-bit nibbles of HIBYTE
ADD LOBYTE, HIBYTE //
ANDI LOBYTE, 0xF //
// third step: reduction modulo 3 = 2^2 - 1
MOV HIBYTE, LOBYTE //
LSR HIBYTE //
LSR HIBYTE //
ANDI LOBYTE, 0x3 //
ADD LOBYTE, HIBYTE //
MOV HIBYTE, LOBYTE //
LSR HIBYTE //
LSR HIBYTE //
ANDI LOBYTE, 0x3 //
ADD LOBYTE, HIBYTE //
// final subtraction of 3, followed by addition of 3 if difference < 0
SUBI LOBYTE, 0x3 //
SBC ZERO, ZERO //
ANDI ZERO, 0x3 // ZERO is now either 0 or 3
ADD LOBYTE, ZERO //
// pop registers from stack
CLR HIBYTE
CLR R1
// that's all folks :-)
RET
.end func