Software self-testing for embedded processor cores based on their instruction set, is a topic of increasing interest since it provides an excellent test resource partitioning technique for sharing the testing task of complex Systems-on-Chip (SoC) between slow, inexpensive testers and embedded code stored in memory cores of the SoC. We introduce an efficient methodology for processor cores self-testing which requires knowledge of their instruction set and Register Transfer (RT) level description. Compared with functional testing methodologies proposed in the past, our methodology is more efficient in terms of fault coverage, test code size and test application time. Compared with recent software based structural testing methodologies for processor cores, our methodology is superior in terms of test development effort and has significantly smaller code size and memory requirements, while virtually the same fault coverage is achieved with an order of magnitude smaller test application time.