[pierrot]

En la arquitectura Intel 8086 (de principios de la década del 80'), los registros eran de 16 bits. Si las direcciones de memoria se hubiesen guardado en un registro solo, la memoria que dicha arquitectura hubiese podido direccionar habría sido solamente de \( 2^{16} \) Bytes = \( 64 \) KiB que era muy poco incluso para esa época. Con el propósito de direccionar 1 MiB de RAM (y no cambiar el tamaño de los registros), lo que se les ocurrió fue inventar un modelo de memoria segmentado utilizando dos registros para formar cada dirección efectiva de memoria: un registro de segmento y un registro de desplazamiento. De esa manera, la dirección efectiva (o absoluta) que la CPU enviaba por el bus de direcciones se calculaba de esta manera:

Dirección absoluta = (Segmento * 16) + Desplazamiento

Por ejemplo, para la dirección absoluta 12345h una posibilidad era elegir segmento=1234h, desplazamiento=5h, o también era válido segmento=1000h, desplazamiento=2345h. En el primer caso, la dirección segmentada se denota por 1234h:0005h y en el segundo, 1000h:2345h. Si el resultado de la suma (Segmento * 16) + Desplazamiento excedía los 20 bits, éste se truncaba y la CPU se quedaba con los 20 bits menos significativos.

La pregunta es: para una dirección de memoria absoluta dada (en el rango 00000h a FFFFFh), ¿cuántas posibles combinaciones de segmento y desplazamiento hay?

En esta página viene contestada la pregunta en el siguiente párrafo, pero no dice por qué.

As a matter of fact there may be up to 4,096 different Segment:Offset pairs for addressing a single byte in Memory; depending upon its particular location. For Absolute addresses 0h through FFEFh ( 0 through 65,519 ), the number of different pairs can be computed as follows: Divide the Absolute address by 16 ( which shifts all the hex digits one place to the right ), then throw away any fractional remainder and add 1. This is the same thing as saying: Add 1 to the Segment number if the Offset is 000Fh (15) or less. For example, the byte in memory referenced by the Segment:Offset pair 0040:0000 has a total of 41h (or 65) different pairs that might be used. For the Absolute address 7C00h, which was mentioned above, there's a total of: 7C00 / 10h --> 7C0 + 1 = 7C1 (or 1,985) relative ways to address this same memory location using Segment:Offset pairs. For the Absolute addresses from FFF0h (65,520) all the way through FFFFFh (1,048,575), there will always be 4,096 Segment:Offset pairs one could use to refer to these addresses! That's a little over 88% of the memory that can be accessed using Segment:Offsets. The last 65,520 bytes that can be accessed by this method are collectively called the High Memory Area (HMA). For each 16 bytes higher in the HMA that we point to, there is one less Segment:Offset pair available to reference that paragraph.

[pierrot]

No quiero que el contexto informático que le di a mi pregunta esconda la naturaleza matemática del problema. Supondré de aquí en más que estoy trabajando en el sistema hexadecimal (de manera que si por ejemplo escribo 10, me estoy refiriendo al número decimal 16). Mi pregunta es:

Dado un número entre 00000 y FFFFF, lo quiero expresar de la forma s*10+d donde s y d tienen cuatro cifras y el resultado de la anterior suma se trunca a 5 cifras (o si se quiere, s*10+d mod 100000) . ¿Cuántas posibles elecciones para s y d tengo?

[Luis Fuentes]

Hola

 Permíteme que lo escriba en decimal, me siento más cómodo.

 Sea \( n \) (la dirección absoluta) entero, con \( 0\leq n\leq 16^5-1 \).

 Por el algortimo de la división, podemos escribirlo como:

 \( n=16c+r \) con \( 0\leq r<16 \) y \( 0\leq c<16^4-1 \)

 Tendríamos que \( r \) es el menor desplazamiento posible para representar nuestro número.

 A partir de ahí cualquier otra posible representación es de la forma:

\(  n=16\underbrace{(c-x)}_{seg}+\underbrace{(r+16x)}_{despl} \)

 Donde \( 0\leq x\leq 16^3-1 \) y también \( x\leq c \).

 Por tanto distinguimos dos casos:

 1) Si \( c< 16^{3}-1 \) el número posible de representaciones (el número posible de valores de \( x \), \( 0\leq x\leq c \)) es \( c+1 \).

 2) Si \( c\geq 16^{3}- \)1 entonces el número posible de representaciones (el número posible de valores de \( x \), \( 0\leq x\leq 16^3-1 \)) es \( 16^3-1+1=4096 \).

 La cota \( c< 16^3-1 \) equivale a \(  c=16^3-2 \), y a su vez a que \( n\leq (16^3-2)\cdot 16+15=65519 \).

 Por otra parte la división  \( n=16c+r \), trabajando en Hexadecimal es directa: el resto es la última cifra y el cociente las anteriores.

Saludos.

[pierrot]

Sea \( n \) (la dirección absoluta) entero, con \( 0\leq n\leq 16^5-1 \).

 Por el algortimo de la división, podemos escribirlo como:

 \( n=16c+r \) con \( 0\leq r<16 \) y \( 0\leq c<16^4-1 \)

 Tendríamos que \( r \) es el menor desplazamiento posible para representar nuestro número.

 A partir de ahí cualquier otra posible representación es de la forma:

\(  n=16\underbrace{(c-x)}_{seg}+\underbrace{(r+16x)}_{despl} \)

 Donde \( 0\leq x\leq 16^3-1 \) y también \( x\leq c \).

¿Por qué \( x\leq 16^3-1 \)?

Edito: Ya lo vi. Es por la restricción de que \( x \) no sea tan grande que el desplazamiento se exceda de cuatro dígitos. Entonces ha de ser \( r+16x\leq 16^4-1 \) o sea \( 16x\leq 16^4-(r+1) \) o sea \( x\leq 16^3-\dfrac{r+1}{16} \) luego \( x\leq \left\lfloor 16^3-\dfrac{r+1}{16}\right\rfloor=16^3-1 \).

[pierrot]

Muchas gracias, el_manco. Veo que tu solución concuerda con lo que se dice en esa página. Pero tengo una objeción.

\(  n=16\underbrace{(c-x)}_{seg}+\underbrace{(r+16x)}_{despl} \)

Con este tipo de descomposiciones, el segmento más grande que consideras para formar una dirección absoluta dada, es \( c \). ¿Pero cuál sería el número si se permitieran segmentos más grandes? Por ejemplo, para FFEF una posible descomposición es s=FFFF y d=FFFF ya que al hacer s*10+d nos da 10FFEF que al truncarlo a 5 dígitos, nos queda FFEF.

[Luis Fuentes]

Hola

Muchas gracias, el_manco. Veo que tu solución concuerda con lo que se dice en esa página. Pero tengo una objeción.

\(  n=16\underbrace{(c-x)}_{seg}+\underbrace{(r+16x)}_{despl} \)

Con este tipo de descomposiciones, el segmento más grande que consideras para formar una dirección absoluta dada, es \( c \). ¿Pero cuál sería el número si se permitieran segmentos más grandes? Por ejemplo, para FFEF una posible descomposición es s=FFFF y d=FFFF ya que al hacer s*10+d nos da 10FFEF que al truncarlo a 5 dígitos, nos queda FFEF.

En ese caso, el número máximo que podemos representar (sin truncar) es:

\( 16(16^4-1)+16^4-1=16^5+16^4-17 \)

que truncado queda:

\( 16^4-17=65519 \)

Entonces para \( n\leq 65519 \) a las representaciones anteriores habría que añadir, las de \( n+16^5 \). Y ahora el razonamiento sería análogo. Tendríamos:

\( n+16^5=16c+r \) con \( 0\leq r<16 \)

y de ahí representaciones de la forma:

\( 16(c-x)+(r+16x) \)

con \( 0\leq x\leq 16^3-1 \) (ahora está asegurado que \( c>16^3-1 \), porque estamos trabajando con \( n+16^5 \)).

Tendríamos por tanto \( 16^3=4096 \) representaciones más.

En resumen y si no me equivocado (¡revísalo!) permitiendo truncar tenemos:

- Si \( n\leq 65519 \), \( 4096+c+1  \)representaciones, donde \( c=[n/16] \).
- Si \( n>65519 \) entonces tenemos \( 4096  \)representaciones.

Saludos.

[pierrot]

En ese caso, el número máximo que podemos representar (sin truncar) es:

\( 16(16^4-1)+16^4-1=16^5+16^4-17 \)

que truncado queda:

\( 16^4-17=65519 \)

De acuerdo. De hecho, es la dirección absoluta que señalé en mi mensaje anterior (la FFEF).

Entonces para \( n\leq 65519 \) a las representaciones anteriores habría que añadir, las de \( n+16^5 \).

De acuerdo.

Y ahora el razonamiento sería análogo.

Es análogo pero creo que hay que tener un poco de cuidado.

Tendríamos:

\( n+16^5=16c+r \) con \( 0\leq r<16 \)

y de ahí representaciones de la forma:

\( 16(c-x)+(r+16x) \)

con \( 0\leq x\leq 16^3-1 \) (ahora está asegurado que \( c>16^3-1 \), porque estamos trabajando con \( n+16^5 \)).

El problema que yo veo ahí es que ese \( c \) que se obtiene por el algoritmo de la división podría ser de 5 dígitos. Y entonces, por ejemplo, cuando cuentas la representación que se obtiene para \( x=0 \), estarías contando una representación inválida porque el número de segmento tendría 5 dígitos y eso no puede ser (tanto segmento como desplazamiento son de 4 dígitos). Lo hago con el ejemplo de mi mensaje anterior: la dirección FFEF. Queremos contar las representaciones de \( n+16^5 \), o sea, FFEF+100000=10FFEF. La igualdad

\( n+16^5=16c+r \) con \( 0\leq r<16 \)

en hexadecimal sería: 10FFEF = 10 * 10FFE + F. O sea que \( c \) en este caso sería 10FFE que es de 5 dígitos. Cuando se consideran representaciones del tipo:

\( 16(c-x)+(r+16x) \)

con el ánimo de que \( c-x \) sea el segmento, y \( r+16x \) el desplazamiento, hay que fijarse bien en la cota inferior de \( x \). Por ejemplo, para \( x=0 \) se estaría contando la dirección segmentada 10FFE:F que no es válida pues el segmento tiene 5 cifras (por tanto, no "cabe" en 16 bits que son 4 dígitos hexadecimales).

Muchas gracias por tu ayuda, el_manco. La verdad es que a mí me habían abrumado todos estos detalles, pero tu planteo me ha dejado claro el camino. La pregunta que debo contestar es: En Intel 8086, ¿cuántas combinaciones de valores diferentes de segmento y desplazamiento pueden utilizarse para referenciar la misma dirección de memoria?. A priori, me parecía una cuenta sencilla, pero cuando lo empecé a pensar en realidad es bastante más complejo de lo que creí. Así que empecé a navegar por la Web buscando una respuesta y no me terminó de convencer ninguno de los sitios que leí. Y aquí es cuando uno constata (no sin un dejo de tristeza) el poco rigor matemático que tienen los informáticos aún en los cálculos más elementales  .

[Luis Fuentes]

Hola

El problema que yo veo ahí es que ese \( c \) que se obtiene por el algoritmo de la división podría ser de 5 dígitos. Y entonces, por ejemplo, cuando cuentas la representación que se obtiene para \( x=0 \), estarías contando una representación inválida porque el número de segmento tendría 5 dígitos y eso no puede ser (tanto segmento como desplazamiento son de 4 dígitos). Lo hago con el ejemplo de mi mensaje anterior: la dirección FFEF. Queremos contar las representaciones de \( n+16^5 \), o sea, FFEF+100000=10FFEF.

De acuerdo. Entonces tendríamos que quedarnos con las representaciones del tipo (y pongo mejor \( c'=[(n+16^5)/16] \) para no confundirlo con el \( c=[n/16] \) de mi primera respuesta):

\( 16(c'-x)+(r+16x) \)

con \( c'-x\leq (16^4-1) \) y \( x\leq 16^3-1 \), es decir, \( 16^3-1\geq x\geq c'-(16^4-1) \).

Por tanto tenemos \( 16^3-1-c'+16^4 \) representaciones adicionales con \( c'=[(n+16^5)/16]=[n/16]+16^4 \).

Se las sumamos a las \( [n/16]+1 \) que teníamos y quedan:

\( 16^3-1-c'+16^4+[n/16]+1=16^3-1-[n/16]-16^4+16^4+[n/16]+1=16^3=4096 \)

Es decir como era de esperar permitiendo el truncamiento...¡todas las direcciones pueden representarse del mismo número de formas: 4096!. 

En realidad podríamos haber razonado esto desde el principio notando que aquí:

\( n=16c+r \) con \( 0\leq r<16 \) y \( 0\leq c<16^4-1 \)

 Tendríamos que \( r \) es el menor desplazamiento posible para representar nuestro número.

 A partir de ahí cualquier otra posible representación es de la forma:

\(  n=16\underbrace{(c-x)}_{seg}+\underbrace{(r+16x)}_{despl} \)

 Donde \( 0\leq x\leq 16^3-1 \) y también \( x\leq c \).

 Precisamente cuando \( x>c \), es decir, cuando \( c-x<0 \) podemos sustituir esa representación por una con truncamiento:

\( n+16^5=16((c-x)+16^4)+(16x+r) \)

 Con lo cual seguimos completando las \( 4096 \) posibles representaciones.

Saludos.

[pierrot]

¡Muchas gracias, el_manco! 

Lo paso en limpio:

Sea \( n \) la dirección absoluta, con \( 0\leq n\leq 16^5-1 \). Por el algoritmo de la división,

\( n=16c+r \) con \( 0\leq r<16 \) y \( 0\leq c<16^4-1 \)

(Si \( n \) está en hexadecimal, \( r \) es el último dígito y \( c \) el número formado por los anteriores.)

A partir de aquí, cualquier otra representación tiene la forma:

\( n=16\underbrace{(c-x)}_\mbox{sgto.}+\underbrace{r+16x}_\mbox{desp.} \)

donde \( \fbox{$0\leq x\leq 16^3-1$} \).

Spoiler

Esto es porque pretendemos que \( r+16x \) sea el desplazamiento, y por tanto \( r+16x\leq 16^4-1 \) o sea \( 16x\leq 16^4-(r+1) \) o sea \( x\leq 16^3-\dfrac{r+1}{16} \) luego \( x\leq \left\lfloor 16^3-\dfrac{r+1}{16}\right\rfloor=16^3-1 \)

[cerrar]

Ahora veamos que para cada \( x \), tenemos un segmento y un desplazamiento determinados, por lo tanto hay 4096 combinaciones de valores diferentes de segmento y desplazamiento. Para ver esto, hay que distinguir dos casos:

• \( c<16^3-1 \), o equivalentemente \( 0\leq n\leq 65519 \).
  Spoiler

  Para ver a qué condición en \( n \) equivale \( c<16^3-1 \), nos fijamos en el máximo \( n \) para el cual \( c=16^3-2 \), que es \( n=16(16^3-2)+15=65519 \)

  [cerrar]
  
  En este caso, partimos el rango \( 0\leq x\leq 16^3-1 \) en dos:
  
  
  • \( 0\leq x\leq c \). Basta tomar \( s=c-x\geq 0 \) y \( d=r+16x \).
    
    
  • \( c+1\leq x\leq 16^3-1 \). Ahora \( c-x<0 \) por lo que no lo podemos tomar como segmento. Pero valiéndonos de la igualdad
    
    \( n+16^5=16\big((c-x)+16^4\big)+r+16x \)
    
    podemos considerar una representación con truncamiento eligiendo \( s=(c-x)+16^4 \) y \( d=16x+r \).
    
    
  
  
• \( c\geq 16^3-1 \), o equivalentemente \( 65520\leq n\leq 16^5-1 \).
  Spoiler

  Para ver a qué condición en \( n \) equivale \( c\geq 16^3-1 \), nos fijamos en el mínimo \( n \) para el cual \( c=16^3-1 \), que es \( n=16(16^3-1)=65520 \)

  [cerrar]
  
  En este caso, siempre se cumple que \( c-x\geq 0 \) luego elegimos \( s=c-x \) y \( d=r+16x \).
  

Es decir como era de esperar permitiendo el truncamiento...¡todas las direcciones pueden representarse del mismo número de formas: 4096!. 

Ésa fue la respuesta que encontré en distintos lugares, pero no estaba bien argumentado y no me convencía  .