SAR (0x1d)

shift (top) - number of bit positions to shift
value - 256-bit value (interpreted as signed i256)

value >> shift (arithmetic, sign-fill)

shift < 256:
  - Positive: value >> shift (zero-fill, same as SHR)
  - Negative: value >> shift (one-fill, preserves sign)
shift >= 256:
  - Positive: 0
  - Negative: 0xFFFF...FFFF (-1)

import { sar } from '@tevm/voltaire/evm/bitwise';
import { createFrame } from '@tevm/voltaire/evm/Frame';

// Positive value: SAR behaves like SHR
const value = 0x1000n;  // MSB = 0 (positive)
const frame = createFrame({ stack: [4n, value] });
const err = sar(frame);

console.log(frame.stack[0].toString(16));  // '100' (zero-filled)

// Negative value: SAR preserves sign
const negativeValue = (1n << 255n) | 0xFFn;  // MSB = 1 (negative)
const frame = createFrame({ stack: [4n, negativeValue] });
sar(frame);

// High bits filled with 1s (sign-extended)
const expectedMsb = 1n << 251n;  // MSB shifted to bit 251
console.log((frame.stack[0] >> 251n) & 1n);  // 1 (sign preserved)

// SAR correctly divides signed integers
// -16 / 4 = -4
const minussixteen = (1n << 256n) - 16n;  // Two's complement of -16
const frame = createFrame({ stack: [2n, minussixteen] });
sar(frame);

const minusFour = (1n << 256n) - 4n;
console.log(frame.stack[0] === minusFour);  // true (-4 in two's complement)

// Shift >= 256 on negative → -1 (all ones)
const negativeValue = 1n << 255n;  // -2^255 in two's complement
const frame = createFrame({ stack: [256n, negativeValue] });
sar(frame);

const allOnes = (1n << 256n) - 1n;
console.log(frame.stack[0] === allOnes);  // true (-1)

// Shift >= 256 on positive → 0
const positiveValue = (1n << 254n);  // Large positive
const frame = createFrame({ stack: [256n, positiveValue] });
sar(frame);

console.log(frame.stack[0]);  // 0n

// Same negative value, different shifts
const negValue = 1n << 255n;  // MSB set

// SHR: logical (zero-fill)
const frameSHR = createFrame({ stack: [1n, negValue] });
shr(frameSHR);
console.log(frameSHR.stack[0] === (1n << 254n));  // true (bit 254, positive)

// SAR: arithmetic (sign-fill)
const frameSAR = createFrame({ stack: [1n, negValue] });
sar(frameSAR);
const expectedSAR = (1n << 255n) | (1n << 254n);  // Both bits 254 and 255 set
console.log(frameSAR.stack[0] === expectedSAR);  // true (still negative)

// Before Constantinople: expensive!
result = int256(value) / int256(2 ** shift)  // SDIV (5 gas) + EXP (10 + 50/byte gas)
// Total: 15-1615 gas

// After Constantinople: cheap!
assembly { result := sar(shift, value) }  // 3 gas

// Shifting zero always yields zero (sign = 0)
const frame = createFrame({ stack: [100n, 0n] });
sar(frame);

console.log(frame.stack[0]);  // 0n

// No shift = identity
const value = 0xDEADBEEFn;
const frame = createFrame({ stack: [0n, value] });
sar(frame);

console.log(frame.stack[0] === value);  // true

// -1 (all ones) shifted remains -1
const minusOne = (1n << 256n) - 1n;
const frame = createFrame({ stack: [100n, minusOne] });
sar(frame);

console.log(frame.stack[0] === minusOne);  // true (sign-extended)

// MIN_INT256 = -2^255
const MIN_INT = 1n << 255n;
const frame = createFrame({ stack: [1n, MIN_INT] });
sar(frame);

// -2^255 / 2 = -2^254 (sign-extended)
const expected = (1n << 255n) | (1n << 254n);
console.log(frame.stack[0] === expected);  // true

// MAX_INT256 = 2^255 - 1 (MSB = 0, all other bits = 1)
const MAX_INT = (1n << 255n) - 1n;
const frame = createFrame({ stack: [1n, MAX_INT] });
sar(frame);

// Result: zero-filled (positive)
const expected = (1n << 254n) - 1n;
console.log(frame.stack[0] === expected);  // true

// Shift negative value to leave only sign bit
const negValue = (1n << 255n) | 0xFFFFn;
const frame = createFrame({ stack: [255n, negValue] });
sar(frame);

const allOnes = (1n << 256n) - 1n;
console.log(frame.stack[0] === allOnes);  // true (all 1s)

// Value with only bit 254 set (large positive)
const value = 1n << 254n;  // MSB = 0
const frame = createFrame({ stack: [1n, value] });
sar(frame);

// Result: 1 << 253 (still positive)
console.log(frame.stack[0] === (1n << 253n));  // true

// SAR is invalid before Constantinople
const frame = createFrame({
  stack: [4n, 0xFF00n],
  hardfork: 'byzantium'
});
const err = sar(frame);

console.log(err);  // { type: "InvalidOpcode" }

const frame = createFrame({ stack: [4n] });
const err = sar(frame);

console.log(err);  // { type: "StackUnderflow" }

const frame = createFrame({ stack: [4n, 0xFF00n], gasRemaining: 2n });
const err = sar(frame);

console.log(err);  // { type: "OutOfGas" }

// Efficient signed division
function divideBy8(int256 value) pure returns (int256) {
    assembly {
        result := sar(3, value)  // Divide by 2^3 = 8
    }
    return result;
}

// Extract signed 16-bit value from lower bits
function extractInt16(uint256 packed) pure returns (int16) {
    uint256 raw = packed & 0xFFFF;  // Extract 16 bits

    // Sign-extend to 256 bits
    int256 extended;
    assembly {
        // Shift left to MSB, then SAR back (sign-extends)
        extended := sar(240, shl(240, raw))
    }

    return int16(extended);
}

// Q64.64 fixed-point division by 2
function halfFixedPoint(int128 value) pure returns (int128) {
    // value is Q64.64: upper 64 bits integer, lower 64 fractional
    // Shift right 1 to divide by 2 (preserves sign)
    assembly {
        result := sar(1, value)
    }
    return int128(result);
}

// Extend sign from bit position
function signExtend(uint256 value, uint256 bitPos) pure returns (uint256) {
    require(bitPos < 256, "bit position out of range");

    // Shift to align sign bit with MSB, then SAR back
    uint256 shift = 255 - bitPos;
    assembly {
        value := sar(shift, shl(shift, value))
    }
    return value;
}

// Check if packed signed value is negative
function isNegative(uint256 packed, uint256 bitWidth) pure returns (bool) {
    require(bitWidth > 0 && bitWidth <= 256, "invalid bit width");

    // Extract sign bit
    uint256 signBit = (packed >> (bitWidth - 1)) & 1;
    return signBit == 1;
}

import { describe, it, expect } from 'vitest';
import { sar } from './sar.js';

describe('SAR (0x1d)', () => {
  it('shifts positive value (same as SHR)', () => {
    const frame = createFrame({ stack: [4n, 0x1000n] });
    expect(sar(frame)).toBeNull();
    expect(frame.stack[0]).toBe(0x100n);
  });

  it('sign-extends negative value', () => {
    const negValue = 1n << 255n;  // MSB set
    const frame = createFrame({ stack: [1n, negValue] });
    expect(sar(frame)).toBeNull();

    // Result should have both bit 255 and 254 set (sign-extended)
    const expected = (1n << 255n) | (1n << 254n);
    expect(frame.stack[0]).toBe(expected);
  });

  it('divides negative by power of 2', () => {
    // -16 / 4 = -4
    const minus16 = (1n << 256n) - 16n;
    const frame = createFrame({ stack: [2n, minus16] });
    expect(sar(frame)).toBeNull();

    const minus4 = (1n << 256n) - 4n;
    expect(frame.stack[0]).toBe(minus4);
  });

  it('returns -1 for shift >= 256 on negative', () => {
    const negValue = 1n << 255n;
    const frame = createFrame({ stack: [256n, negValue] });
    expect(sar(frame)).toBeNull();

    const minusOne = (1n << 256n) - 1n;
    expect(frame.stack[0]).toBe(minusOne);
  });

  it('returns 0 for shift >= 256 on positive', () => {
    const posValue = 1n << 254n;
    const frame = createFrame({ stack: [256n, posValue] });
    expect(sar(frame)).toBeNull();
    expect(frame.stack[0]).toBe(0n);
  });

  it('handles zero shift (identity)', () => {
    const value = 0x123456n;
    const frame = createFrame({ stack: [0n, value] });
    expect(sar(frame)).toBeNull();
    expect(frame.stack[0]).toBe(value);
  });

  it('shifts -1 remains -1', () => {
    const minusOne = (1n << 256n) - 1n;
    const frame = createFrame({ stack: [100n, minusOne] });
    expect(sar(frame)).toBeNull();
    expect(frame.stack[0]).toBe(minusOne);
  });

  it('handles MIN_INT256', () => {
    const MIN_INT = 1n << 255n;
    const frame = createFrame({ stack: [1n, MIN_INT] });
    expect(sar(frame)).toBeNull();

    // -2^255 / 2 = -2^254 (sign-extended)
    const expected = (1n << 255n) | (1n << 254n);
    expect(frame.stack[0]).toBe(expected);
  });

  it('differs from SHR on negative values', () => {
    const negValue = 1n << 255n;

    // SHR: logical (zero-fill)
    const frameSHR = createFrame({ stack: [1n, negValue] });
    shr(frameSHR);

    // SAR: arithmetic (sign-fill)
    const frameSAR = createFrame({ stack: [1n, negValue] });
    sar(frameSAR);

    expect(frameSHR.stack[0]).not.toBe(frameSAR.stack[0]);
    expect(frameSHR.stack[0]).toBe(1n << 254n);  // Positive
    expect(frameSAR.stack[0]).toBe((1n << 255n) | (1n << 254n));  // Negative
  });

  it('returns InvalidOpcode before Constantinople', () => {
    const frame = createFrame({
      stack: [4n, 0xFF00n],
      hardfork: 'byzantium'
    });
    expect(sar(frame)).toEqual({ type: 'InvalidOpcode' });
  });

  it('returns StackUnderflow with insufficient stack', () => {
    const frame = createFrame({ stack: [4n] });
    expect(sar(frame)).toEqual({ type: 'StackUnderflow' });
  });

  it('returns OutOfGas when insufficient gas', () => {
    const frame = createFrame({ stack: [4n, 0xFF00n], gasRemaining: 2n });
    expect(sar(frame)).toEqual({ type: 'OutOfGas' });
  });
});

// CRITICAL: Using wrong shift for signed values
function divideSignedBy4(int256 value) pure returns (int256) {
    assembly {
        result := shr(2, value)  // WRONG! Treats as unsigned
    }
    return result;
}

// CORRECT: Use SAR for signed
function divideSignedBy4(int256 value) pure returns (int256) {
    assembly {
        result := sar(2, value)  // Preserves sign
    }
    return result;
}

// Example:
// value = -16 (0xFFFF...FFF0)
// SHR: 0x3FFF...FFFC (large positive, WRONG!)
// SAR: 0xFFFF...FFFC (-4, correct)

// SAR rounds toward negative infinity (floor division)
function divideSigned(int256 a, int256 b) pure returns (int256) {
    // Only use SAR if b is a power of 2
    require(isPowerOf2(uint256(b)), "not power of 2");

    uint256 shift = log2(uint256(b));
    assembly {
        result := sar(shift, a)
    }
    return result;
}

// Note: -7 / 4 using SAR = -2 (floor)
//       -7 / 4 in Solidity SDIV = -1 (truncate toward zero)

// WRONG: Assuming SAR on unsigned creates signed
function makeNegative(uint256 value) pure returns (int256) {
    assembly {
        value := sar(1, value)  // Doesn't make value negative!
    }
    return int256(value);
}

// SAR interprets existing sign bit, doesn't change sign

// DANGEROUS: Mixing signed and unsigned shifts
function process(uint256 value, bool isSigned) pure returns (uint256) {
    assembly {
        switch isSigned
        case 0 { value := shr(4, value) }  // Unsigned
        case 1 { value := sar(4, value) }  // Signed
    }
    return value;
}

// Risk: Type confusion if isSigned doesn't match value's actual signedness