Write an -bit binary string as , where each and is most significant. Its unsigned interpretation and two's complement interpretation areEquivalently, . The ranges are through and through , respectively. The same stored bits can therefore denote different integers depending on the chosen interpretation.
A logical right shift by moves into position and fills the high positions with zero. Its unsigned interpretation isMeanwhile the original unsigned interpretation decomposes asBy integer division, , exactly the unsigned quotient. Thus the source instruction puts the required quotient into
r1. This is a proof from binary representation, rather than an assumption that every kind of right shift implements every kind of division. The displayed bit argument applies to , with endpoint operations implemented as a copy or zero where appropriate.For a 32-bit machine word and , use a left bit shift followed by a logical right shift:The left shift discards all but the lowest bits and moves those retained bits to the top. The logical right shift returns them to their original positions and fills the rest with zero. Hence
lsls r1, r0, #(32-k)
lsrs r1, r1, #(32-k)r1 contains , the remainder identified in (b). For the remainder is zero; for it is , so these endpoints can be handled directly.On a reduced instruction set computer, a bit mask such as may not fit an instruction's immediate field. Masking may therefore require materializing the constant in another processor register, possibly using several instructions or a memory load. Small shift counts are directly encodable, so the two shifts can save code space, a temporary processor register, or a load. This is an architecture-dependent advantage, rather than a universal speed claim. The source's compact instruction forms support these immediate shifts, while their bitwise AND form takes its other operand from a processor register.[ref]
Thumb 16-bit instruction set quick reference by Arm. page 1, Logical and Shift/rotate tables
Let , let , and let denote the least nonnegative residue. Here is a signed 32-bit two's complement value. The source instructions, annotated with their derived values, are:The first instruction is an arithmetic right shift, so it replicates the sign bit. The second is a logical right shift, turning the all-one word into . The paired shifts then extract the low ten bits, as in (c). Their effect is the residue of even if its two's complement interpretation is negative, because divides the word modulus . The adjusted value is representable for every input: positive inputs are unchanged, and negative inputs gain only .
rem1024:
asrs r3, r0, #31 // r3 = -s: all zero bits or all one bits
lsrs r3, r3, #22 // r3 = b = 1023*s
adds r0, r0, r3 // r0 = a+b
lsls r0, r0, #22 // r0 has word value (a+b)*2^22 modulo 2^32
lsrs r0, r0, #22 // r0 = u = (a+b) modulo 1024, in 0,...,1023
subs r0, r0, r3 // r0 = u-b
bx lr // return u-bFor , , so the return value is the usual nonnegative remainder . For , put as a mathematical integer, and write with . If , then and the return value is zero. If , thenThese are precisely the remainders for C integer division, whose quotient truncates towards zero. In every case the result has the dividend's sign or is zero, has magnitude below , and satisfies . The proof includes the smallest representable input: was used only in mathematical reasoning, not as an overflowing machine operation.[ref]
C11 committee draft N1570. section 6.5.5 paragraph 6, quotient truncation and the quotient–remainder identity
Use the same bias, then an arithmetic right shift by ten:An arithmetic right shift of a two's complement integer computes division rounded down. For , this already equals truncation towards zero. For , the signed power-of-two division by biasing identity isIndeed, writing with makes the adjusted numerator ; its quotient rounded down is for every , including zero. Thus the code returns the signed quotient in all cases and contains no data-dependent branch. The final
div1024:
asrs r3, r0, #31 // -1 when a<0, otherwise 0
lsrs r3, r3, #22 // b = 1023 when a<0, otherwise 0
adds r0, r0, r3 // a+b, representable for every signed input
asrs r0, r0, #10 // floor((a+b)/1024)
bx lrbx lr simply returns to the caller.Use a message-passing mutual exclusion server with an A client sends
owner field and a FIFO queue. A request includes its client's identity. The server handles one received message at a time, and a client has at most one outstanding request. The following pseudocode assumes reliable message passing and compliant clients:owner = NONE
waiting = empty FIFO queue
forever:
(kind, client) = receive_from_any_client()
if kind == REQUEST:
waiting.push_back(client)
else if kind == RELEASE:
assert client == owner
owner = NONE
if owner == NONE and not waiting.empty():
owner = waiting.pop_front()
send(owner, GRANT)REQUEST, waits for GRANT, runs its complete animation, and sends RELEASE before making another request.The invariant proving mutual exclusion is: at most one client has received an unreturned grant, and that client is
owner. Only the final block issues a grant, and it first requires no current owner. A valid release removes that ownership. Since clients use the display only while holding a grant, simultaneous use is impossible. The FIFO queue prevents accepted requests from being overtaken by later ones. With eventual message delivery, continued server execution, and finite animations, each accepted request is eventually served; these progress assumptions are separate from the safety invariant.Use two FIFO queues, one for each priority class, and perform nonpreemptive strict-priority arbitration whenever the display becomes free:The same ownership invariant proves mutual exclusion. Among requests already accepted by the server, every pending urgent request takes precedence over every ordinary one. Each class retains its own arrival order. A newly received urgent request goes ahead of waiting ordinary requests but waits for the current animation's
owner = NONE
ordinary = empty FIFO queue
urgent = empty FIFO queue
forever:
message = receive_from_any_client()
if message.kind == REQUEST:
assert message.priority in {0, 1}
if message.priority == 1:
urgent.push_back(message.client)
else:
ordinary.push_back(message.client)
else if message.kind == RELEASE:
assert message.client == owner
owner = NONE
if owner == NONE:
if not urgent.empty():
owner = urgent.pop_front()
else if not ordinary.empty():
owner = ordinary.pop_front()
if owner != NONE:
send(owner, GRANT)RELEASE; the given protocol has no interruption or revocation operation.This is strict priority at dispatch, based on requests the server has received. Requests still in transit cannot influence a decision. If the transport provides a mailbox-draining operation, the server may also collect all currently delivered requests before dispatching; the two-FIFO queue selection rule remains the same.
Strict priority does not guarantee starvation freedom for ordinary clients under an endless supply of urgent work. If urgent traffic eventually stops, accepted requests have only finitely many earlier requests, and all service times are finite, every pending ordinary request is eventually granted. Guaranteeing ordinary progress under unlimited urgent traffic would require a different fairness policy, such as limiting consecutive urgent grants; that would relax strict priority.
A LIFO stack can make waiting clients starve. Suppose client waits at the bottom of the stack. Before each current owner releases, a fresh client submits a request. That newest request is pushed above and is selected next. Every animation can finish promptly while waits forever.
This is LIFO starvation: service completion alone does not ensure starvation freedom. A FIFO queue prevents newer same-priority requests from passing , whereas replacing either priority-class FIFO queue by a LIFO stack adds this problem even within one priority class. Strict priority can already starve ordinary work, as in (b); the LIFO stack introduces a further unfairness that can also affect urgent work.
Use a three-sample run detector. Just before clock edge , let two stored bits and hold the input values at edges and . Initialise both to zero. With input , definePrimes denote the next stored state, with all assignments simultaneous at the clock edge. The output is the logical conjunction of the present input and its two preceding samples. By induction on clock edges, the stated interpretation of is maintained, proving the required behaviour. Two bits of state suffice.
Store two bits: the output , initially zero, and an
armed bit , initially one. Define the synchronous sequential circuit byHere is exclusive or, and the input restriction excludes conflicting commands. The output is the current stored .When armed, a sampled toggles and clears . Further samples leave the output unchanged. A sampled sets without changing , allowing a later to toggle it again. The same clock edge cannot both rearm and trigger because are never simultaneously high. Thus the first toggles from zero to one, and subsequent toggles each require a new followed by a later .
Share the input-history bits of (a) between a high-run detector and a low-run detector. With the two preceding input samples, putThese detector outputs are mutually exclusive. Feed them into (b). An explicit four-bit synchronous sequential circuit, with initial state , isEvery right-hand side uses the old state and the current input. In particular, the run detectors' combinational outputs are sampled by the toggle module at that same edge; there is no extra pipeline stage.
The first three consecutive high samples make at the third edge, toggling and clearing . Continuing high input cannot toggle it again. Only three consecutive low samples can make and rearm it; interrupted low runs do not suffice. After rearming, a new three-sample high run produces the next toggle. This proves the debounced toggle switch behaviour, including rejection of short high and low disturbances.
The debounced toggle switch rejects interrupted runs, toggles on the third consecutive high sample, and rearms only on the third consecutive low sample; stored outputs are shown just after each clock edge
. Details. 
Four state bits are necessary and sufficient. For each output value, distinguish three armed situations, remembering a trailing high run of length , and three disarmed situations, remembering a trailing low run of length . Thus a direct minimal behavioural description hasAll twelve situations are reachable. Different output values are immediately distinguishable. Within an armed group, a suitable number of high samples distinguishes the three run lengths by when the next toggle occurs. Within a disarmed group, a suitable number of low samples followed by three highs distinguishes the three rearming distances. An armed situation and a disarmed situation of the same output value are distinguished by an all-high continuation: the armed one eventually toggles and the disarmed one does not. Hence these twelve situations cannot be merged in a finite-state machine implementing the specification.
The shared-history design in (c) uses four bits, meeting this lower bound. Its sixteen encoded states have some behaviourally equivalent histories, so its encoding need not use only twelve combinations. Building two separate copies of (a) plus the two-bit module (b) would use six state-bearing elements; sharing the input history saves two.
Articles by others on the same topic
There are currently no matching articles.