Your browser does not support JavaScript! Skip to main content
Free 30-day trial Customer portal Careers DO-178C Handbook
 
Rapita Systems
 

Industry leading verification tools & services

Rapita Verification Suite (RVS)

  RapiTest - Unit/system testing   RapiCover - Structural coverage analysis   RapiTime - Timing analysis (inc. WCET)   RapiTask - Scheduling visualization   RapiCoverZero - Zero footprint coverage analysis   RapiTimeZero - Zero footprint timing analysis   RapiTaskZero - Zero footprint scheduling analysis

Multicore verification

  MACH178   Multicore Timing Solution   RapiDaemons

Services

  V & V Services   Qualification   Training   Tool Integration  Support

Industries

  Aerospace (DO-178C)   Automotive (ISO 26262)   Space

Other

  RTBx   Mx-Suite   Software licensing   Product life cycle policy  RVS development roadmap

Latest from Rapita HQ

Latest news

RVS 3.18 Launched
Solid Sands partners with Rapita Systems
Danlaw Acquires Maspatechnologies - Expanding Rapita Systems to Spain
Rapita co-authored paper wins ERTS22 Best paper award
View News

Latest from the Rapita blog

Measuring response times and more with RapiTime
Why mitigating interference alone isn’t enough to verify timing performance for multicore DO-178C projects
There are how many sources of interference in a multicore system?
Supporting modern development methodologies for verification of safety-critical software
View Blog

Latest discovery pages

do178c DO-178C Guidance: Introduction to RTCA DO-178 certification
matlab_simulink MATLAB® Simulink® MCDC coverage and WCET analysis
code_coverage_ada Code coverage for Ada, C and C++
amc-20-193 AMC 20-193
View Discovery pages

Upcoming events

Aerospace Tech Week Europe 2023
2023-03-29
Aeromart Montreal 2023
2023-04-04
Certification Together International Conference
2023-05-10
View Events

Technical resources for industry professionals

Latest White papers

DO178C Handbook
Efficient Verification Through the DO-178C Life Cycle
A Commercial Solution for Safety-Critical Multicore Timing Analysis
Compliance with the Future Airborne Capability Environment (FACE) standard
View White papers

Latest Videos

Streamlined software verification with RVS 3.18
Sequence analysis with RapiTime
Visualize call dependencies with RVS thumbnail
Visualize call dependencies with RVS
Analyze code complexity thumbnail
Analyze code complexity with RVS
View Videos

Latest Case studies

Supporting ISO 26262 ASIL D software verification for EasyMile
RapiCover’s advanced features accelerate the certification of military UAV Engine Control
Front cover of whitepaper collins
Delivering world-class tool support to Collins Aerospace
View Case studies

Other Downloads

 Webinars

 Brochures

 Product briefs

 Technical notes

 Research projects

Discover Rapita

Who we are

The company menu

  • About us
  • Customers
  • Distributors
  • Locations
  • Partners
  • Research projects
  • Contact us

US office

+1 248-957-9801
info@rapitasystems.com
Rapita Systems, Inc.
41131 Vincenti Ct.
Novi
MI 48375
USA

UK office

+44 (0)1904 413945
info@rapitasystems.com
Rapita Systems Ltd.
Atlas House
Osbaldwick Link Road
York, YO10 3JB
UK

Spain office

+34 930 46 42 72
info@rapitasystems.com
Rapita Systems S.L.
Parc UPC, Edificio K2M
c/ Jordi Girona, 1-3, Office 306-307
Barcelona 08034
Spain

Working at Rapita

Careers

Careers menu

  • Current opportunities & application process
  • Working at Rapita
Back to Top

Supporting Duff's Device in RVS

Breadcrumb

  1. Home
  2. Blog
  3. Supporting Duff's Device in RVS
2016-06-10

Nested “case” labels are an obscure feature of C, and not often seen. However, examples do exist, typically hidden deep in standard library functions and our customers come across them from time to time. Here's a little article about how we recently brought support for them into RVS.

Nested “case” labels in practical C programs

For instance, the well-known sqlite3 library contains the following code:

switch( pOp->opcode ){
...
case OP_SorterNext: {  /* jump */
  VdbeCursor *pC;
  int res;

  pC = p->apCsr[pOp->p1];
  ...
  res = 0;
  ...
  goto next_tail;
case OP_PrevIfOpen:    /* jump */
case OP_NextIfOpen:    /* jump */
  if( p->apCsr[pOp->p1]==0 ) break;
  /* Fall through */
case OP_Prev:          /* jump */
case OP_Next:          /* jump */
  ...
  pC = p->apCsr[pOp->p1];
  res = pOp->p3;

This is found within the “sqlite3VdbeExec” function and forms the core of sqlite3's execution engine. Note that the local variables “pC” and “res” are shared between several different branches of the case; the label “case OP_PrevIfOpen:” is one of many that are nested within this block. Writing the code in this way made it possible to share these local variables between multiple “case” branches without needing to share them with the whole “sqlite3VdbeExec” function. Arguably, this makes the code clearer and easier to maintain.

Duff's Device

Duff's Device is a notorious example of a “switch” statement with nested case labels. It consists of a “switch” and a “do {} while” loop, in which the elements of the “switch” and loop are interleaved as follows:

    int n = (count + 7) / 8;
    switch (count % 8) {
    case 0: do { *to = *from++;
    case 7:      *to = *from++;
    case 6:      *to = *from++;
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
            } while (--n > 0);
    }

In this example, “Duff's Device” copies memory, eight elements at a time. However, the total number of elements copied does not need to be divisible by eight. The first iteration can copy fewer than eight elements. This is arranged by entering the “do {} while” loop in the middle, via the nested “case” labels “case 7” through “case 1”. This avoids the need for a second group of copying statements, which would only be used when the number of elements to copy is not a multiple of eight.

“Duff's Device” is rarely used, though it frequently appears as an example of strange code that is nevertheless accepted by a C compiler. However, as the example of sqlite3 illustrates, Duff-like constructs do appear occasionally in practical C programs. Like the much-maligned “goto” statement, the nested “case” feature may be used with caution by C experts in order to write simpler or faster code.

Nested “case” labels and RVS

In version 3.5, RVS tools will gain support for “switch” constructs where “case” labels are nested. This means that Duff's Device (and constructs like it) are now supported. RapiTime timing analysis and RapiCover coverage analysis are both possible.

This is tricky to achieve because with nested switch/case, the program's control flow cannot easily be represented as a tree. The “switch” statement and the “do {} while” loop are interleaved: neither is inside of the other. Therefore, there is no straightforward way to represent the worst-case execution time of the “switch” statement. And for RapiCover, there is no easy way to determine which branches have been taken, because the entry points may be anywhere within the “switch”.

My solution to the problem was to reuse the existing support within RVS for “goto” statements. An early analysis pass searches each “switch” statement for nested “case” labels and treats them as “goto” labels. For each “case” label found in this way, a virtual “case” element is added as a child of the “switch” statement, containing a “goto” pointing at the appropriate label.

For example, if we had some code like this:

switch (x) {
   case 1:  if (y > 0) {
               example_1 ();
   case 2:     example_2 (); break;
            }
   default: example_others (); break;
}

The source code is effectively represented internally using a syntax tree like this:

Source code represented using a syntax tree

The modification means that all “case” labels have the same parent. For the purposes of all subsequent analysis stages, a “switch” with nested “case” labels is just like any other “switch”.

Conclusion

From time to time, there are situations where it is useful to nest “case” labels inside other blocks. Code may be simplified significantly by expert use of such techniques, much as expert use of “goto” can make code clearer. We work hard to support the way our customers work, and I'm pleased that RVS tools will now analyse this kind of construct.

DO-178C webinars

DO178C webinars

White papers

DO178C Handbook Efficient Verification Through the DO-178C Life Cycle
A Commercial Solution for Safety-Critical Multicore Timing Analysis
Compliance with the Future Airborne Capability Environment (FACE) standard
5 key factors to consider when selecting an embedded testing tool
  • Solutions
    • Rapita Verification Suite
    • RapiTest
    • RapiCover
    • RapiTime
    • RapiTask
    • MACH178

    • Verification and Validation Services
    • Qualification
    • Training
    • Integration
  • Latest
  • Latest menu

    • News
    • Blog
    • Events
    • Videos
  • Downloads
  • Downloads menu

    • Brochures
    • Webinars
    • White Papers
    • Case Studies
    • Product briefs
    • Technical notes
    • Software licensing
  • Company
  • Company menu

    • About Rapita
    • Careers
    • Customers
    • Distributors
    • Industries
    • Locations
    • Partners
    • Research projects
    • Contact
  • Discover
    • AMC 20-193
    • What is CAST-32A?
    • Multicore Timing Analysis
    • MC/DC Coverage
    • Code coverage for Ada, C & C++
    • Embedded Software Testing Tools
    • Aerospace Software Testing
    • Automotive Software Testing
    • Certifying eVTOL
    • DO-178C
    • WCET Tools
    • Worst Case Execution Time
    • Timing analysis (WCET) & Code coverage for MATLAB® Simulink®

All materials © Rapita Systems Ltd. 2023 - All rights reserved | Privacy information | Trademark notice Subscribe to our newsletter