Announcement

Collapse

Forum etiquette

Our mission ...

This forum is part of our mission to promote the preservation of vintage computers through education and outreach. (In real life we also run events and have a museum.) We encourage you to join us, participate, share your knowledge, and enjoy.

This forum has been around in this format for over 15 years. These rules and guidelines help us maintain a healthy and active community, and we moderate the forum to keep things on track. Please familiarize yourself with these rules and guidelines.


Remain civil and respectful

There are several hundred people who actively participate here. People come from all different backgrounds and will have different ways of seeing things. You will not agree with everything you read here. Back-and-forth discussions are fine but do not cross the line into rude or disrespectful behavior.

Conduct yourself as you would at any other place where people come together in person to discuss their hobby. If you wouldn't say something to somebody in person, then you probably should not be writing it here.

This should be obvious but, just in case: profanity, threats, slurs against any group (sexual, racial, gender, etc.) will not be tolerated.


Stay close to the original topic being discussed
  • If you are starting a new thread choose a reasonable sub-forum to start your thread. (If you choose incorrectly don't worry, we can fix that.)
  • If you are responding to a thread, stay on topic - the original poster was trying to achieve something. You can always start a new thread instead of potentially "hijacking" an existing thread.



Contribute something meaningful

To put things in engineering terms, we value a high signal to noise ratio. Coming here should not be a waste of time.
  • This is not a chat room. If you are taking less than 30 seconds to make a post then you are probably doing something wrong. A post should be on topic, clear, and contribute something meaningful to the discussion. If people read your posts and feel that their time as been wasted, they will stop reading your posts. Worse yet, they will stop visiting and we'll lose their experience and contributions.
  • Do not bump threads.
  • Do not "necro-post" unless you are following up to a specific person on a specific thread. And even then, that person may have moved on. Just start a new thread for your related topic.
  • Use the Private Message system for posts that are targeted at a specific person.


"PM Sent!" messages (or, how to use the Private Message system)

This forum has a private message feature that we want people to use for messages that are not of general interest to other members.

In short, if you are going to reply to a thread and that reply is targeted to a specific individual and not of interest to anybody else (either now or in the future) then send a private message instead.

Here are some obvious examples of when you should not reply to a thread and use the PM system instead:
  • "PM Sent!": Do not tell the rest of us that you sent a PM ... the forum software will tell the other person that they have a PM waiting.
  • "How much is shipping to ....": This is a very specific and directed question that is not of interest to anybody else.


Why do we have this policy? Sending a "PM Sent!" type message basically wastes everybody else's time by making them having to scroll past a post in a thread that looks to be updated, when the update is not meaningful. And the person you are sending the PM to will be notified by the forum software that they have a message waiting for them. Look up at the top near the right edge where it says 'Notifications' ... if you have a PM waiting, it will tell you there.

Copyright and other legal issues

We are here to discuss vintage computing, so discussing software, books, and other intellectual property that is on-topic is fine. We don't want people using these forums to discuss or enable copyright violations or other things that are against the law; whether you agree with the law or not is irrelevant. Do not use our resources for something that is legally or morally questionable.

Our discussions here generally fall under "fair use." Telling people how to pirate a software title is an example of something that is not allowable here.


Reporting problematic posts

If you see spam, a wildly off-topic post, or something abusive or illegal please report the thread by clicking on the "Report Post" icon. (It looks like an exclamation point in a triangle and it is available under every post.) This send a notification to all of the moderators, so somebody will see it and deal with it.

If you are unsure you may consider sending a private message to a moderator instead.


New user moderation

New users are directly moderated so that we can weed spammers out early. This means that for your first 10 posts you will have some delay before they are seen. We understand this can be disruptive to the flow of conversation and we try to keep up with our new user moderation duties to avoid undue inconvenience. Please do not make duplicate posts, extra posts to bump your post count, or ask the moderators to expedite this process; 10 moderated posts will go by quickly.

New users also have a smaller personal message inbox limit and are rate limited when sending PMs to other users.


Other suggestions
  • Use Google, books, or other definitive sources. There is a lot of information out there.
  • Don't make people guess at what you are trying to say; we are not mind readers. Be clear and concise.
  • Spelling and grammar are not rated, but they do make a post easier to read.
See more
See less

Right Hand Shift (RHS) of Bits using an ALU, 74F181

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

    Right Hand Shift (RHS) of Bits using an ALU, 74F181

    Hi, I am building a TTL computer using the 74F181 ALU. I am fairly far along in the project and I am coding now in machine code. One of the things that has come up as an issue pretty quickly is that there is no right hand bit shift available. The ALU has the usual ADD, Subtract, Increment, Decrement and many other logic functions, such as AND, NAND, OR, XOR, NOR, XNOR, NOT, etc.

    My system data bus is 12 bits, so what would be especially useful is moving nibbles around. For example, moving the top nibble (the tribble?) to the bottom. Here is an example:

    1011 0000 0000 becomes 0000 0000 1011

    I could add some more hardware to do this, but my boards are already pretty jam-packed. The only way I have thought to do this in code is by doing a 16 case comparison. (4 bits = 16 cases).

    Does anyone know any tricks using the math and logic functions to shift to the right? I'm not finding much with the search engines. Thanks! Michael

    Here is a link to my project.

    http://www.mtmscientific.com/stack.html

    #2
    Other than two 8 bit parts with a latch and 3state output, I don't know of anything other than a bunch of left shifts.
    Using some RAM, add to it self and move the carry bit in the output RAM location. That gives a loop of 4 to move things followed by an or operation to recombine. The output location need to be 0'd firrst, of course.
    Dwight

    Comment


      #3
      If one of your functions is an end-around left rotate, you have your answer already. If you can test for carryout of an end-off left shift, you can synthesize a right shift by re-building the number from the carryouts and dropping the last iteration. Not pretty, but it's possible. If you don't have a way to check for carryouts, but can test for the presence of a 1 in the high-order bit, you can do the same--just test before shifting.

      You could also test each bit individually without shifting and rebuild the result less the low-order bit. If you know ahead of time that your argument will tend to be range-restricted (i.e. less than 12 significant bits), you can shortcut some of the loop by testing for zeroes in groups of bits. None of these approaches is particularly wonderful in terms of cycles. You can also divide the operand into subfields and perform a table-lookup on each subfield and combine the results. On a 12 bit operand, you could divide the operand into 2 six-bit fields and perform table lookup in a 64-word table.

      A simple left shift is, in my opinion, not as useful as a single right shift, given the presence of addition and subtraction. After all, a left shift of A is equivalent to computing A+A.

      Note also, that I'm talking about a logical right shift, not an arithmetic sign-extension right shift.
      Last edited by Chuck(G); March 24, 2021, 11:37 AM.

      Comment


        #4
        How do you treat the most significant carry. If it goes to a register to be used in future operations you have what you need to do as Chuck and I have said.
        Using Ti's notes on the 181.

        C=0
        F=A+A
        F=A+A+C
        F=A+A+C
        F=A+A+C
        F=A+0+C

        6 steps in the micro code.
        That should work.
        Dwight

        Comment


          #5
          You guys put me on the right track! I have a Jump that uses the 12th bit as a flag, the Left shift using the Addition (A+A), and I can set the Least Significant Bit using the Increment instruction. All in a pretty tight loop. Thanks.

          As an aside, what I would really enjoy tinkering with is a TTL barrel shifter. (A combinatorial circuit that does bit shifting without being clocked.) For some of my other jump instructions I am using the output from 74LS686, which does a real time equality and magnitude comparison of A and B in the ALU.

          Michael

          Comment


            #6
            12-bits / PDP-8?!

            This is one reason why the LD12 (PDP-8 lookalike) uses 74194s for the accumulator. The 74194 is a 4-bit bidirectional universal shift register with a parallel load. The 74181 chips perform the ALU functional unit and the accumulator register itself performs the rotate left and right independent of the ALU.

            Dave

            Comment


              #7
              Only slightly off-the-subject, but if you're looking for a full-functioned ALU IC, you might want to look at the SN74S481 Described here. 48 pin DIP, with shift-left/right and a potload of other functionality, while still retaining the '181 basic functions. The DG Nova used several of these.

              Comment


                #8
                When I was first playing with my NC4000 processor ( a Stack processor ), I needed to chop 16 bit data into a byte value to send to 8 bit ports. I added two 74ls374s to swap bytes, rather than shifting the data in a loop. The NC4000 has a number of short addressing modes that only take one 16 bit for both the fetch/store and a short address.
                By placing the address at FFFF, it only took 2 instructions to swap bytes, using -1, a short literal, as the target address. A nibble swap can be done the same way.

                I like Dave's idea of using a 74194 ( 74LS194 is available ). It is just that it is still one clock per bit shift. Good for things like divide and multiply but still slow for real barrel shifting. There are a lot of specialized bit twizzlling that can be done as a specialized address, rather than a special microcode.
                Dwight

                Comment


                  #9
                  Barrel shifters using MUXes, are neat but are logic hogs, which is why the 8080 had only single-bit shifts.

                  One approach uses 2:1 muxes in several stages, each stage selecting a shift by a certain number bits or pass-through. So, if you start with a stage that can either shift by one bit or none at the bottom, the next layer can be a shift by 2 bits or none, the next, by 4 bits or none and the final stage can shift by 8 bits or none. Note that you'll need 12 2:1 muxes for each stage. You see what I mean by "logic hog" for a single function...

                  However, as others have noted, a simple multi-bit, say 4 or 6 bits, shift function requires only a single stage of 12 muxes and can cut down on overhead considerably. One can also use a n-way MUX to select between, say, 0, 2 and 4 bit shifts.

                  Another logic hog is a "count the ones" tree. The CDC 6000 series had this instruction as a dedicated functional unit. I've been told that it was specifically requested by some (unnamed) intelligence agencies for crypto purposes.
                  Last edited by Chuck(G); March 25, 2021, 09:47 AM.

                  Comment


                    #10
                    Originally posted by Chuck(G) View Post
                    Another logic hog is a "count the ones" tree. The CDC 6000 series had this instruction as a dedicated functional unit. I've been told that it was specifically requested by some (unnamed) intelligence agencies for crypto purposes.
                    And also why the Cray 1 had population count and leading zero count instructions.

                    Comment


                      #11
                      Well, after all, the same guy (Seymour) designed both. "Count leading zeroes" is a subfunction of normalized floating point arithmetic, so less of a surprise.

                      The STAR, had arbitrary-length "count ones", "count leading equals" as well as a raft of other bit-oriented instructions--but then, memory was bit-addressable. It was a Thornton (he of the 6400) design.

                      Comment


                        #12
                        Originally posted by Chuck(G) View Post
                        Only slightly off-the-subject, but if you're looking for a full-functioned ALU IC, you might want to look at the SN74S481 Described here. 48 pin DIP, with shift-left/right and a potload of other functionality, while still retaining the '181 basic functions. The DG Nova used several of these.
                        That chip apparently used unobtainium technology. Can't find it anywhere other than on a data sheet!

                        Comment


                          #13
                          They're around--they were expensive and not terribly plentiful. However, the Am2901 does pretty much the same thing and can still be found and [u]is[/b] plentiful, comparatively. Cheap enough to cascade into a 12 bit ALU.

                          Comment

                          Working...
                          X