Skip to content

Instantly share code, notes, and snippets.

@ponceto

ponceto/README.md

Last active January 17, 2025 10:29
Show Gist options
  • Save ponceto/ef20caeaa3843d4a56a06f70ee005a8f to your computer and use it in GitHub Desktop.
Save ponceto/ef20caeaa3843d4a56a06f70ee005a8f to your computer and use it in GitHub Desktop.
Download ZIP
Russian Multiplication for the Z80 CPU
Raw
README.md

Russian Multiplication for the Z80 CPU

This is a very simple and generic implementation of the russian multiplication method for the Z80 CPU, designed to deal with 16-bits multiplications.

The file mul.cc contains a generic C++ implementation of the russian algorithm with some unit tests.

The file mul.asm contains a hand-written (not tested) implementation of the algorithm in Z80 assembly, based on the C++ version.

Raw
mul.asm
;
; mul.asm - Copyright (c) 2024-2025 - Olivier Poncet
;
; 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 2 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 <http://www.gnu.org/licenses/>.
;
; ----------------------------------------------------------------------------
; auto mul(uint16_t multiplicand, uint16_t multiplicator) -> int16_t
;
; Input:
; BC: the multiplicand
; DE: the multiplicator
;
; Output:
; HL: the result
;
; Timing:
; Min: 40 t-states (10us at 4MHz)
; Max: ~1184 t-states (~296us at 4MHz)
; ----------------------------------------------------------------------------
; +--------------------------------------------------------+--------------+--------------+
mul: ; | Description | Min T-States | Max T-States |
; +--------------------------------------------------------+--------------+--------------+
ld HL, 0 ; | initialize the result to zero | 10 | 10 |
; | | | |
ld A, D ; | load MSB of DE into the accumulator | 4 | 4 |
or E ; | test LSB of DE with MSB (inclusive OR) | 4 | 4 |
jr Z, mul_end ; | if DE (the multiplicator) is zero, go to the end | 7 | 12 |
; | | | |
mul_loop: ; | | | |
bit 0, E ; | test if DE (the multiplicator) is odd or even | 8 | 8 |
jr Z, mul_shift ; | if DE (the multiplicator) is even, go to shift | 7 | 12 |
; | | | |
add HL, BC ; | compensate HL (the result) with BC (the multiplicand) | 11 | 11 |
; | | | |
mul_shift: ; | | | |
srl D ; | shift DE to the right: shift right logical of D | 8 | 8 |
rr E ; | shift DE to the right: rotate right through carry of E | 8 | 8 |
; | | | |
sla C ; | shift BC to the left: shift left artithmetic of C | 8 | 8 |
rl B ; | shift BC to the left: rotate left through carry of B | 8 | 8 |
; | | | |
ld A, D ; | load MSB of DE into the accumulator | 4 | 4 |
or E ; | test LSB of DE with MSB (inclusive OR) | 4 | 4 |
jr NZ, mul_loop ; | if DE (the multiplicator) is not zero, iterate | 7 | 12 |
; | | | |
mul_end: ; | | | |
ret ; | return the result | 10 | 10 |
; +--------------------------------------------------------+--------------+--------------+
Raw
mul.cc
/*
* mul.cc - Copyright (c) 2024-2025 - Olivier Poncet
*
* 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 2 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 <http://www.gnu.org/licenses/>.
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdint>
#include <iostream>
#include <stdexcept>
// ---------------------------------------------------------------------------
// Russian Multiplication Method
// ---------------------------------------------------------------------------
auto mul(uint16_t value, uint16_t scale) -> int16_t
{
uint16_t result = 0;
if(scale != 0) {
do {
if((scale & 1) != 0) {
result += value;
}
scale >>= 1;
value <<= 1;
} while(scale != 0);
}
return result;
}
// ---------------------------------------------------------------------------
// Assert
// ---------------------------------------------------------------------------
struct Assert
{
static auto begin(const std::string& group) -> void
{
success_count = 0;
failure_count = 0;
static_cast<void>(fprintf(stdout, "[ TEST ] %s\n", group.c_str()));
static_cast<void>(fflush(stdout));
}
static auto end(const std::string& group) -> void
{
static_cast<void>(fprintf(stdout, "[ DONE ] %s [success=%d, failure=%d]\n", group.c_str(), success_count, failure_count));
static_cast<void>(fflush(stdout));
}
static auto pass() -> const char*
{
++success_count;
return "PASS";
}
static auto fail() -> const char*
{
++failure_count;
return "FAIL";
}
static auto equals(const int expected, const int value) -> bool
{
if(value == expected) {
return true;
}
throw std::runtime_error(std::string("Assert::equals<int>() has failed") + ' ' + '(' + std::to_string(value) + " != " + std::to_string(expected) + ')');
}
static int success_count;
static int failure_count;
};
int Assert::success_count = 0;
int Assert::failure_count = 0;
// ---------------------------------------------------------------------------
// TestGroup
// ---------------------------------------------------------------------------
class TestGroup
{
public:
TestGroup(const std::string& group)
: _group(group)
{
Assert::begin(_group);
}
~TestGroup()
{
Assert::end(_group);
}
void check() const
{
if(Assert::failure_count != 0) {
throw std::runtime_error(_group + ' ' + "has failed!");
}
}
private:
const std::string _group;
};
// ---------------------------------------------------------------------------
// Program
// ---------------------------------------------------------------------------
struct Program
{
static auto check_mul(const int lhs, const int rhs) -> void
{
const int expected = (lhs * rhs);
bool status = false;
int result = 0;
auto pass = [&]() -> void
{
static_cast<void>(fprintf(stdout, "[ %s ] mul(%+d, %+d) -> %+d\n", Assert::pass(), lhs, rhs, result));
static_cast<void>(fflush(stdout));
};
auto fail = [&]() -> void
{
static_cast<void>(fprintf(stdout, "[ %s ] mul(%+d, %+d) -> %+d (expected %+d)\n", Assert::fail(), lhs, rhs, result, expected));
static_cast<void>(fflush(stdout));
};
auto check = [&]() -> void
{
try {
result = mul(lhs, rhs);
status = Assert::equals(expected, result);
}
catch(const std::exception& e) {
status = false;
}
if(status != false) {
pass();
}
else {
fail();
}
};
return check();
}
static auto main() -> void
{
const TestGroup group("« Russian Multiplication Method »");
check_mul(0, 9);
check_mul(1, 8);
check_mul(2, 7);
check_mul(3, 6);
check_mul(4, 5);
check_mul(5, 4);
check_mul(6, 3);
check_mul(7, 2);
check_mul(8, 1);
check_mul(9, 0);
check_mul(-127, -257);
check_mul(-127, +257);
check_mul(+127, -257);
check_mul(+127, +257);
return group.check();
}
};
// ---------------------------------------------------------------------------
// main
// ---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
try {
Program::main();
}
catch(const std::exception& e) {
std::cerr << "fatal error: " << e.what() << std::endl;
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}
// ---------------------------------------------------------------------------
// End-Of-File
// ---------------------------------------------------------------------------
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment