real-time reading of a quadrature encoder at full resolution with only one interrupt on ATmega328
This is just a partial, rushed answer.

You should be able to get a significant speed-up if you define your own
ISR for handling the interrupt, as in:

ISR(INT1_vect) { ... }


The Arduino way of using interrupts is instead

void trigger() { ...}

void setup() {
    attachInterrupt(int_number, trigger, CHANGE);
    ...
}


but this is slow, as it involves the ISR provided by the Arduino core,
which has to locate and call your interrupt handler. The way you wrote
the handler is wrong: either you define a regular function, without the
ISR macro, and go the Arduino way, or you go the plain AVR path and
define the ISR yourself, which should be named INTERRUPT_NAME_vect, in
which case you don't use attachInterrupt(). The way you did it is
probably the slowest you can get, as the compiler will needlessly add an
ISR-type prologue and epilogue to your handler.

As for the maximum frequency, that's hard to assess without testing, but
you may get some idea by reading this answer on interrupt
latency.



Edit: As I stated in my first comment to the question, a pin change
interrupt can be used instead of an external logic gate. Here is how to
do it.

First, one should look at the Arduino Uno pinout and see that:


digital 4 = PD4 = PCINT20
digital 5 = PD5 = PCINT21


Both pins are tied to the pin change interrupt request 2 (PCINT2_vect).
This interrupt can be configured in setup() as follows:

PCMSK2 = _BV(PCINT20)   // enable interrupt on pin PCINT20 = PD4
       | _BV(PCINT21);  // enable interrupt on pin PCINT21 = PD5
PCIFR  = _BV(PCIF2);    // clear interrupt flag
PCICR  = _BV(PCIE2);    // enable pin change interrupt request 2


Now, the interrupt will fire on every change of the logic levels of
inputs&nbsp;4 and&nbsp;5.

Then, in the ISR, the whole port&nbsp;D can be read in a single cycle by
just evaluating the corresponding pin input register, i.e. PIND. With
some shifting and masking, one can get a phase between&nbsp;0 and&nbsp;3
(the count is in Gray code: 0, 1, 3, 2, 0...). From the previous and the
current phase, one can compute the change that needs to be applied to
the counter:

// Handle pin change interrupt request 2.
ISR(PCINT2_vect) {
    static uint8_t previous_phase;
    uint8_t phase = (PIND &gt;&gt; 4) &amp; 0x03;  // read input pins
    counter += encoder_delta(previous_phase, phase);
    previous_phase = phase;
}


The implementation of encoder_delta() is left as an exercise to the
reader. ;-)