How to further improve Safemoon's reflection token transfer? (ERC20/BEP20)

Question

We all know Safemoon's iconic reflection token code, giving every holder a percentage of every fee on buy / sell.

I've already simplified and improved the gas efficiency and the token logic quite a bit, but there is a marked inefficiency in getCurrentSupply() as it loops over each reflection excluded account to get rSupply and tSupply.

This can be avoided by caching rSupply and tSupply as uint256 and updating them on transfer.

However I don't fully understand the logic enough yet to completely refactor it; only partially. Note that I have made all functions public for this test case.

contract Reflectable {

    constructor() {
        _tTotal = 100000000;
        _rTotal = (type(uint).max - (type(uint).max % _tTotal)); 
        _rOwned[msg.sender] = _rTotal; // allocate initial supply to deployer
    }

    mapping (address => uint) internal _rOwned;
    mapping (address => uint) internal _tOwned;
    mapping (address => bool) internal _isFeeExempt;    // excluded from all transfer fees (to or from)
    mapping (address => bool) internal _isExcluded;     // excluded from reflections

    address[] internal _rExcluded;

    uint internal immutable taxPercent = 5;
    uint internal immutable _tTotal;
    uint internal _rTotal; 
    
    function balanceOf(address account) public view virtual returns (uint) {
        return _isExcluded[account] ? _tOwned[account] : tokenFromReflection(_rOwned[account]);
    }

    function transfer(address from, address to, uint amount, bool isFeeExempt) public {
        isFeeExempt = (isFeeExempt || _isFeeExempt[from] || _isFeeExempt[to]);
        uint tFee; // 0
        if (!isFeeExempt) { 
            tFee = (amount * taxPercent) / 100;
        }
        uint rate = _sendTokensSupportingFeeOnTransfer(from, to, amount, (amount - tFee));
        if (tFee > 0) {
            _reflect(tFee * rate);   
        }
    }

    /// NOTE: Requires Solidity 0.8+. Do NOT enclose in unchecked bloc. Emits a {Transfer} event.
    /// @dev Combines Safemoon's `_transferStandard()`, `_transferFromExcluded()`, `_transferToExcluded()`, and `_transferBothExcluded()`.
    function _sendTokensSupportingFeeOnTransfer(
        address from,
        address to,
        uint amount,    // amount to deduct from sender
        uint remainder  // amount to send to receiver (after fee deduction)
    ) public returns (uint rate) {
        require(remainder <= amount);

        rate = _getRate(); // NOTE: R values are always T Values * rate (currentRate)

        _rOwned[from] -= (amount * rate);
        _rOwned[to] += (remainder * rate);

        if (_isExcluded[from]) {
            _tOwned[from] -= amount;
        }
        if (_isExcluded[to]) {
            _tOwned[to] += remainder;
        }
        // emit Transfer(from, to, remainder);
    }

    //////////////////////////////////////// Helper functions /////////////////////////////////////////////////////

    // Gets tokens owned from a reflection balance.
    function tokenFromReflection(uint rAmount) public returns (uint tOwned) {  unchecked  {
        if (rAmount > _rTotal) { revert(); } 
        return (rAmount / _getRate());
    }}

    function _getRate() public returns (uint) {  unchecked  {
        (uint rSupply, uint tSupply) = _getCurrentSupply(); 
        return (rSupply / tSupply);
    }}

    // Safemoon's _getCurrentSupply(), optimised for gas fees.
    // Can be improved further by caching updated total rOwned and total tOwned during transfer preventing a need for looping.
    function _getCurrentSupply() public view returns (uint rSupply, uint tSupply) {  unchecked  {

        (rSupply, tSupply) = (_rTotal, _tTotal);

        uint len = _rExcluded.length; uint rOwned; uint tOwned; address account; 
        for (uint i; i < len; i++) { 
            account = _rExcluded[i];
            (rOwned, tOwned) = (_rOwned[account], _tOwned[account]);

            // this line in particular confuses me:
            if (rOwned > rSupply || tOwned > tSupply) { return (_rTotal, _tTotal); }

            rSupply -= rOwned; 
            tSupply -= tOwned;
        }
        return (rSupply < (_rTotal / _tTotal)) ? (_rTotal, _tTotal) : (rSupply, tSupply);
    }}

    function _reflect(uint rAmount) public {  unchecked  {
        _rTotal -= rAmount;
    }}
}

However there's clear room for improvement here, I'm just not sure what exactly to do

    // optimized
    uint T_TotalExcludedSupply;
    uint R_TotalExcludedSupply;

    function _getRateOptimized() public view virtual returns (uint) {  unchecked  { 
        return (rSupply() / tSupply());
    }}

    function rSupply() public view returns (uint) {} // ?
    function tSupply() public view returns (uint) {} // ?

    function sendReflectedTokensOptimized(address from, address to, uint amount, uint remainder) {
        bool senderIsExcluded = _isExcluded[from];
        bool receiverIsExcluded = _isExcluded[to];

        if (!senderIsExcluded && !receiverIsExcluded) { // both receive reflections

        } else if {!senderIsExcluded && receiverIsExcluded) { // reflect acc, standard acc

        } else if (senderIsExcluded && !receiverIsExcluded) { // standard acc, reflect acc

        } else { // senderIsExcluded && receiverIsExcluded    // standard acc, standard acc 

        }
    }

If anyone's really good at math and can solve this, it would effectively halve the gas cost of reflection token transfers.

Answer 1

The calculations for T_TotalExcludedSupply and R_TotalExcludedSupply might be done like this:

// optimized
uint T_TotalExcludedSupply;
uint R_TotalExcludedSupply;

function _getRateOptimized() public view virtual returns (uint) {  unchecked  { 
    return (rSupply() / tSupply());
}}

function rSupply() internal view returns (uint) {
    return _rTotal - R_TotalExcludedSupply;
}

function tSupply() internal view returns (uint) {
    return _tTotal - T_TotalExcludedSupply;
}

function sendReflectedTokensOptimized(address from, address to, uint amount, uint remainder) {
    bool senderIsExcluded = _isExcluded[from];
    bool receiverIsExcluded = _isExcluded[to];
    uint rate = _getRateOptimized();

    if (!senderIsExcluded && !receiverIsExcluded) { // both receive reflections

    } 
    else if (!senderIsExcluded && receiverIsExcluded) { // reflect acc, standard acc
        T_TotalExcludedSupply += remainder;
        R_TotalExcludedSupply += remainder * rate;
    } 
    else if (senderIsExcluded && !receiverIsExcluded) { // standard acc, reflect acc
        T_TotalExcludedSupply -= amount;
        R_TotalExcludedSupply -= amount * rate;
    } 
    else { // senderIsExcluded && receiverIsExcluded    // standard acc, standard acc 
        T_TotalExcludedSupply -= amount;
        R_TotalExcludedSupply -= amount * rate;
    
        T_TotalExcludedSupply += remainder;
        R_TotalExcludedSupply += remainder * rate;
    }
}

P.S. But I'm not sure if it would effectively halve the gas cost of reflection token transfers.

Answer 2

I can't see how the below could happen if there is no burn or minting mechanism.

if (rOwned > rSupply || tOwned > tSupply) { return (_rTotal, _tTotal); }